The voronoi diagram of three lines

ABSTRACT

We give a complete description of the Voronoi diagram of three lines in R³. In particular, we show that the topology of the Voronoi diagram is invariant for three lines in general position, that is, that are pairwise skew and not all parallel to a common plane. The trisector consists of four unbounded branches of either a non-singular quartic or of a cubic and line that do not intersect in real space. Each cell of dimension two consists of two connected components on a hyperbolic paraboloid that are bounded, respectively, by three and one of the branches of the trisector. The proof technique, which relies heavily upon modern tools of computer algebra, is of interest in its own right. This characterization yields some fundamental properties of the Voronoi diagram of three lines. In particular, we present linear semi-algebraic tests for separating the two connected components of each two-dimensional Voronoi cell and for separating the four connected components of the trisector. This enables us to answer queries of the form, given a point, determine in which connected component of which cell it lies. We also show that the arcs of the trisector are monotonic in some direction. These properties imply that points on the trisector of three lines can be sorted along each branch using only linear semi-algebraic tests.

REFERENCES

• 1: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• 2: F. Aurenhammer and R. Klein. Voronoi diagrams. In JR. Sack and JUrrutia, editors, Handbook of computational geometry, chapter 5, pages 201--290. Elsevier Publishing House, December 1999.
• 3: Eric Berberich , Michael Hemmer , Lutz Kettner , Elmar Schömer , Nicola Wolpert, An exact, complete and efficient implementation for computing planar maps of quadric intersection curves, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064110]
• 4: J.-D. Boissonnat, O. Devillers, S. Pion, M. Teillaud, and M. Yvinec. Triangulations in CGAL. Computational Geometry: Theory and Applications, 22:5--19, 2002.
• 5: Jean-Daniel Boissonnat , Olivier Devillers , René Schott , Monique Teillaud , Mariette Yvinec, Applications of random sampling to on-line algorithms in computational geometry, Discrete & Computational Geometry, v.8 n.1, p.51-71, 1992 [doi>10.1007/BF02293035]
• 6: T.M. Chan, J. Snoeyink, and C.K. Yap. Primal dividing and dual pruning: Output-sensitive construction of four dimensional polytopes and three-dimensional diagram voronoi diagrams. Discrete and Computational Geometry, 18:433--454, 1997.
• 7: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 8: H. Cohen. A course in computational algebraic number theory, volume 138 of Graduate Texts in Mathematics. Springer-Verlag, 3rd edition, Berlin, 1996.
• 9: T. Culver. Computing the Medial Axis of a Polyhedron Reliably and Efficiently. PhD thesis, University of North Carolina at Chapel Hill, 2000.
• 10: Tamal K. Dey , Wulue Zhao, Approximate medial axis as a voronoi subcomplex, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany [doi>10.1145/566282.566333]
• 11: L. Dupont, D. Lazard, S. Lazard, and S. Petitjean. Near-optimal parameterization of the intersection of quadrics: I. The generic algorithm. Research Report n^o 5667, INRIA, Sept. 2005. 36 pages.
• 12: L. Dupont, D. Lazard, S. Lazard, and S. Petitjean. Near-optimal parameterization of the intersection of quadrics: II. A classification of pencils. Research Report n^o 5668, INRIA, Sept. 2005. 37 pages.
• 13: Michal Etzion , Ari Rappoport, Computing Voronoi skeletons of a 3-D polyhedron by space subdivision, Computational Geometry: Theory and Applications, v.21 n.3, p.87-120, March, 2002 [doi>10.1016/S0925-7721(01)00056-6]
• 14: Steven Fortune, Voronoi diagrams and Delaunay triangulations, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 15: Gb/FGb. J.-C. Faugere. http://fgbrs.lip6.fr.
• 16: Kenneth E. Hoff, III , John Keyser , Ming Lin , Dinesh Manocha , Tim Culver, Fast computation of generalized Voronoi diagrams using graphics hardware, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.277-286, July 1999 [doi>10.1145/311535.311567]
• 17: M.I. Karavelas. A robust and efficient implementation for the segment voronoi diagram. In International Symposium on Voronoi Diagrams in Science and Engineering, pages 51--62, 2004.
• 18: John Keyser , Shankar Krishnan , Dinesh Manocha, Efficient and accurate B-rep generation of low degree sculptured solids using arithmetic: II—computation, Computer Aided Geometric Design, v.16 n.9, p.861-882, Oct. 1999 [doi>10.1016/S0167-8396(99)00033-3]
• 19: Vladlen Koltun , Micha Sharir, 3-Dimensional Euclidean Voronoi Diagrams of Lines with a Fixed Number of Orientations, SIAM Journal on Computing, v.32 n.3, p.616-642, 2003 [doi>10.1137/S0097539702408387]
• 20: K. Kurdyka, P. Orro, and S. Simon. Semialgebraic Sard theorem for generalized critical values. Journal of Differential Geometry, 56:67--92, 2000.
• 21: D. Leven and M. Sharir. Intersection and proximity problems and voronoi diagrams. In J.T. Schwartz and C.-K. Yap, editors, Advances in Robotics 1: Algorithmic and Geometric Aspects of Robotics, pages 187--228. Lawrence Erlbaum Associates, Hillsdale, NJ, 1987.
• 22: The Maple System. Waterloo Maple Software. http://www.maplesoft.com.
• 23: V.J. Milenkovic. Robust construction of the voronoi diagram of a polyhedron. In Proceedings of the 5th Canadian Conference on Computational Geometry (CCCG'93), pages 473--478, 1993.
• 24: B. Mourrain, J.--P. Tècourt, and M. Teillaud. On the computation of an arrangement of quadrics in 3D. Computational Geometry: Theory and Applications, 30(2):145--164, 2005. Special issue, 19th European Workshop on Computational Geometry.
• 25: A. Okabe, B. Boots, K. Sugihara, and S.N. Chiu. Spatial Tessellations -- Concepts and Applications of Voronoi Diagrams. John Wiley, 2nd edition, 2000.
• 26: S. Pion and M. Teillaud. 3d triangulations. In CGAL Editorial Board, editor, CGAL-3.2 User and Reference Manual. 2006.
• 27: RAG'Lib: A Library for real algebraic geometry. M. Safey El Din, 2003. http://www--calfor.lip6.fr/~safey/RAGLib/.
• 28: F. Rouillier , M.-F. Roy , M. Safey El Din, Finding at least one point in each connected component of a real algebraic set defined by a single equation, Journal of Complexity, v.16 n.4, p.716-750, Dec. 1, 2000 [doi>10.1006/jcom.2000.0563]
• 29: M. Safey El Din. Generalized critical values and testing sign conditions on a polynomial. In DWang and ZZheng, editors, Proceedings of Mathematical Aspects of Computer and Information Science, pages 61--84. 2006.
• 30: Mohab Safey El Din , Éric Schost, Polar varieties and computation of one point in each connected component of a smooth real algebraic set, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.224-231, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860901]
• 31: M. Safey El Din and E. Schost. Properness defects of projections and computation of one point in each connected component of a real algebraic set. Discrete and Computational Geometry, 32(3):417--430, 2004.
• 32: Elmar Schömer , Nicola Wolpert, An exact and efficient approach for computing a cell in an arrangement of quadrics, Computational Geometry: Theory and Applications, v.33 n.1-2, p.65-97, January 2006 [doi>10.1016/j.comgeo.2004.02.007]
• 33: O. Schwarzkopf and M. Sharir. Vertical decomposition of a single cell in a three-dimensional arrangement of surfaces and its applications. Discrete and Computational Geometry, 18:269--288, 1997.
• 34: C. Segre. Studio sulle quadriche in uno spazio lineare ad un numero qualunque di dimensioni. Mem. della R. Acc. delle Scienze di Torino, 36(2):3--86, 1883.
• 35: R. Seidel. A convex hull algorithm optimal for point sets in even dimensions. M.Sc. thesis, Univ. British Columbia, Vancouver, BC, 1981. Report 81/14.
• 36: M. Sharir. Almost tight upper bounds for lower envelopes in higher dimensions. Discrete and Computational Geometry, 12:327--345, 1994.
• 37: M. Teichmann and S. Teller. Polygonal approximation of voronoi diagrams of a set of triangles in three dimensions. Technical Report 766, Laboratory of Computer Science, MIT, 1997.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Theory

Keywords:
Voronoi diagram, medial axis, quadric surface intersection