Sorting Points Along a Curve

MAPC has been used to sort points along a curve in the plane. This is a key step in certain Voronoi diagram computations.

An example of this is provided in the following picture. A curve is (shown in bold) is intersected with 25 curves of verying degrees and bit lengths (shown in green), producing 52 intersection points within the region of interest. Finding all these intersections takes approximately 100 seconds on a 400 Mhz Pentium II. Once the points have been found, they are sorted in order along the curve in under 1 second.