Robert's Mistakes

Diagram 15: Implicit function / contour plot

Jan 24, 2014

It's a way to visualize the objects of (low-dimensional) real algebraic geometry. The tiny graph in the middle below shows the zero locus for an elliptic curve (that's just a fancy class of polynomials in 2 variables). I'll explain the other image below, please read on.

What's an implicit function? You've seen functions defined like this:

y = x^2

Taking that one as equation we could subtract y and write instead:

x^2 - y = 0 or f(x) - y = 0

The question now is, can we have another function around the y? Like this:

f(x) - g(y) = 0

The answer is, indeed we can! This equation happens to have a circle as zero locus:

x^2 + y^2 - 1 = 0

Digression: One thing i should tell you is that, in principle, we could try to solve the resulting equation again for y. But a 1d function can only return a single value for each x. So we'd get either the upper or the lower half ( branch ) of our circle. But we won't be concerned with that here.

For brevity, i'll write h(x,y) instead of f(x)-g(y) in the following.

First note, on the left, a value is computed. Two numbers in, one number out. So you can understand an implicit function as a height map . Like a map of an island. And the solution (set of points at height zero) is the shoreline. Now how to render these on screen? Here's one way to do it:

Just compute the height for every pixel. If it's zero, draw black, if not, leave it white. To see something you'll usually have to count small heights as zero (say, absolute values |f(x,y)| < epsilon). Larger epsilon gives thicker 'lines' for your curve. Note that the thickness varies with the slope . I placed a nip2 worksheet here:

https://gist.github.com/anonymous/144130be16bb246b7768

This is known as point sampling . Structures of sub-pixel size or big slope may be missed. It's also slow, because the function h(x,y) has to be evaluated for each pixel. Can we do better?

One idea may be to draw positive and negative as black and white. But that will miss noncrossing (or tangent) zeros... One has to take care! An alternative method involves using a root finding algorithm , e.g. Newton's method :

Since the Newton is a 1-dimensional algorithm[¹] it'll only work for a line (or curve if you insist). So we'll have to do this for a bulk of lines to fill our screen (covering the plane). Say, we do this for each horizontal row of pixels (called a scan line ). But again, done naively, you'll get another kind of artifacts (gaps in the curves).

There's also another, even more efficient approach (computing even fewer values of h(x,y)), known under the name marching squares. It employs recursive space partitioning (in this case quadtrees) and a set of rules to guide the division process. The picture in the lowe left shows some quadtree cells. The image to the right shows these rules, telling us how to partition further based on a handful of evaluated values.

To alleviate problems with sub-pixel structures you can always try supersampling. But with the marching squares algorithm, there's no need for an extra supersampling method. It's kind of built-in already.

Note that you'll get another pathology for saddles, but the wikipedia article on marching squares has mo

Okay, so we see a curve showing f(x,y)=0 (the zero locus ) now. But what about the f(x,y)=1 line? Here's a trick to obtain topographic lines for all integral heights:

sin(f(x,y)/pi) = 0

That works pretty well, the slope of sin() near it's zeros is close to 1. That means adding height lines does not change the width (much, for small epsilon).

http://en.wikipedia.org/wiki/Implicit_function

http://en.wikipedia.org/wiki/Marching_squares

You can find nip2 here:

http://www.vips.ecs.soton.ac.uk/index.php?title=Nip2

[¹] Some root finding algorithms work well with complex numbers. +Owen Maresh has been experimenting with root finders and i'd like to recommend his series of phase plots he calls "Metarizogeneous functions" :

A phase plot also displays single 1d values for each 2d coordinate, even though complex functions in general map 2d parameters to 2d values.

implicit #function #plot #diagram #mathematics

The marching squares picture is from a paper called "A Bayesian approach to strong lensing modelling of galaxy clusters" available here:

http://iopscience.iop.org/1367-2630/9/12/447/fulltext/

The rules are by Djexplo on wikipedia, currently visible on it's marching squares page.

http://en.wikipedia.org/wiki/File:Marchingsquaresalgorithm.png