What will be provided in the library:

• K_POLY classes - to store and manipulate basic polynomials
• ROOT1s - A univariate root determination class based on Sturm sequences, and incorporating speedups based on sign of the polynomial and floating-point approximations.
• ROOT2s - A bivariate root determination class based on Milne's Sturm sequences, and incorporating the speedups already implemented based on floating point approximation and the already implemented univariate case
• K_POINT - A class to smoothly incorporate 4 types of 2 dimensional points within a single framework. The types of points represented are:
  • X and Y coordinates are known exactly
  • X coordinate is known exactly, Y coordinate is known in an (open) interval
  • Y coordinate is known exactly, X coordinate is known in an (open) interval
  • X and Y coordinate is contained within an (open) box
  K_POINTs incorporate ROOT1 or ROOT2 as needed. The types of operations that can be performed on K_POINTs include:
  • Obtaining a floating-point approximation to the point
  • Determining upper and lower bounds (a bounding box) for the point
  • Finding all points arising from intersections of two bivariate polynomials (either within a given region or anywhere in the real plane), or points arising from when one coordinate is known but the other is a root of some polynomial
  • Classifying a point with respect to a polynomial
  • Comparing two points in either dimension to find which is greater (an answer of UNKNOWN is possible here)
  • Refining the precision to which we know a point. There are a few ways of doing this:
    • Halving the bounding box size in either (or both) coordinates
    • Reducing bounding box size to a certain number of bits of precision in either (or both) directions
    • Shrinking the bounding box by a certain factor or to a certain size in either (or both) directions
    • Cutting the bounding box at a specified value in either (or both) coordinates.
  • Separating two points that have overlapping bounding boxes (as long as they're not equal)
  • Sorting the points in one coordinate or another
  • UNIMPLEMENTED - Checking true equality of two points
  • A few other less commonly useful operations
• KCURVE - A class to deal with algebraic plane curves. These are clipped curves - not just the zero set of the defining polynomial. Among the routines available are:
  • Finding whether a point known to lie on the defining polynomial is on this particular curve
  • Splitting a curve into two other curves given a point on the curve
  • Finding all intersections with the zero set of some other polynomial
  • Finding a bounding box for the entire curve
  • Determining the topology of the curve
  • Subdividing the curve so that the bouding boxes of its segments do not overlap those of another curve.
  • Determining whether a K_POINT lies within the region defined by a closed loop of curves.
• Sign of determinant computation - this is broken out into its own section
• ROOT3 - ??? I don't know the status of Tim's code to know exactly what can be done, here.
• A few minor miscellaneous classes, such as ones to handle boxes (NOT boxes with roots inside) in 2D or 3D. Queries are things like whehter two boxes overlap, one is contained within the other, etc. The unique part of these is that the boxes may be infinite or may be open/closed. Also includes some floating-point conversion stuff that might not be minor, but I haven't looked much at. In addition, there's some vandermonde code and that sort of thing.
• Possibly include some patch, surface, or solid routines. I"m leaning AGAINST this now, though, since it would take too much debugging.

What simple applications can be used as examples:

• Finding all real intersections of two polynomials (too simple?)
• Comparing two points arising from totally different sources (too simple?)
• Determining whether a point lies within a trimmed region of a patch
• Ordering some points along a curve
• Finding loops within a region
• Clipping one set of curves to another (may take some work to implement - easier would be clipping a single curve to another.)
• Algebraic decomposition of a set of polynomials. May take a lot of work.
• 3-D application depending on the state of Tim's code.

What remains to be done:

• Debug what's there a little more - some parts are well tested, others haven't been tested much at all.
• Checking true equality between two points
• Handling border cases for ROOT2s. Note: This could be solved by the next item on this list:
• Switching over to the univariate-only approach.
• Implementing the applications we decide on.
• Library packaging issues: separating the code we want to release from the rest and bundling it together. Writing user documentation, some code documentation, and providing example programs.
• That's all I see at the moment, but I might think of more as time goes on.