Search

International audience; PTOPO is a MAPLE package computing the topology and describing the geometry of a parametric plane curve. The algorithm behind PTOPO constructs an abstract graph that is isotopic to the curve. PTOPO exploits the benefits of the parametric representation and performs all computations in the parameter space using exact computing. PTOPO computes the topology and visualizes the curve in less than a second for most examples in the literature.

We consider the problem of computing the topology and describing the geometry of a parametric curve in Rn. We present an algorithm, PTOPO, that constructs an abstract graph that is isotopic to the curve in the embedding space. Our method exploits the benefits of the parametric representation and does not resort to implicitization. Most importantly, we perform all computations in the parameter space and not in the implicit space. When the parametrization involves polynomials of degree at most d and maximum bitsize of coefficients τ, then the worst case bit complexity of PTOPO is OB (nd6 + nd5 τ + d4 (n2 + nτ) + d3 (n2τ + n3) + n3d2τ). This bound matches the current record bound OB (d6 + d5 τ) for the problem of computing the topology of a planar algebraic curve given in implicit form. For planar and space curves, if N = max{d, τ}, the complexity of PTOPO becomes OB (N6), which improves the state-of-the-art result, due to Alcazar and Diaz-Toca [CAGD'10], by a factor of N10. However, visualizing the curve on top of the abstract graph construction, increases the bound to OB (N7). We have implemented PTOPO in maple for the case of planar curves. Our experiments illustrate its practical nature.

Voronoi diagrams are a fundamental geometric data structure for obtaining proximity relations. We consider collections of axis-aligned orthogonal polyhedra in two and three-dimensional space under the max-norm, which is a particularly useful scenario in certain application domains. We construct the exact Voronoi diagram inside an orthogonal polyhedron with holes defined by such polyhedra. Our approach avoids creating full-dimensional elements on the Voronoi diagram and yields a skeletal representation of the input object. We introduce a complete algorithm in 2D and 3D that follows the subdivision paradigm relying on a bounding-volume hierarchy; this is an original approach to the problem. The complexity is adaptive and comparable to that of previous methods. Under a mild assumption it is \(O(n/ \varDelta + 1/\varDelta ^2)\) in 2D or \(O(n\alpha ^2/\varDelta ^2 +1/\varDelta ^3)\) in 3D, where n is the number of sites, namely edges or facets resp., \(\varDelta \) is the maximum cell size for the subdivision to stop, and \(\alpha \) bounds vertex cardinality per facet. We also provide a numerically stable, open-source implementation in Julia, illustrating the practical nature of our algorithm.