Identifying and approximating monotonous segments of algebraic curves using support function representation
Abstract
Algorithms describing the topology of real algebraic curves search primarily the singular points and they are usually based on algebraic techniques applied directly to the curve equation. We adopt a different approach, which is primarily based on the identification and approximation of smooth monotonous curve segments, which can in certain cases cross the singularities of the curve.
We use not only the primary algebraic equation of the planar curve but also (and more importantly) its implicit support function representation. This representation is also used for an approximation of the segments.
This way we obtain an approximate graph of the entire curve which has several nice properties. It approximates the curve within a given Hausdorff distance.
The actual error can be measured efficiently and behaves as O(N-3) where N is the number of segments. The approximate graph is rational and has rational offsets.
In the simplest case it consists of arc segments which are efficiently represented via the support function. The question of topological equivalence of the approximate and precise graphs of the curve is also addressed and solved using bounding triangles and axis projections.
The theoretical description of the whole procedure is accompanied by several examples which show the efficiency of our method.