Article

The predicates for the Voronoi diagram of ellipses

Authors:

Ioannis Z. Emiris,

Elias P. Tsigaridas,

George M. TzoumasAuthors Info & Claims

SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry

Pages 227 - 236

https://doi.org/10.1145/1137856.1137891

Published: 05 June 2006 Publication History

Abstract

This paper examines the computation of the Voronoi diagram of a set of ellipses in the Euclidean plane. We propose the first complete algorithms, under the exact computation paradigm, for the predicates of an incremental algorithm: κ₁ decides which one of 2 given ellipses is closest to a given exterior point; κ₂ decides the position of a query ellipse relative to an external bitangent line of 2 given ellipses; κ₃ decides the position of a query ellipse relative to a Voronoi circle of 3 given ellipses; κ₄ determines the type of conflict between a Voronoi edge, defined by 4 given ellipses, and a query ellipse. The paper is restricted to non-intersecting ellipses, but the extension to arbitrary ones is possible.The ellipses are input in parametric representation or constructively in terms of their axes, center and rotation. For κ₁ and κ₂ we derive optimal algebraic conditions, solve them exactly and provide efficient implementations in C++. For κ₃ we compute a tight bound on the number of complex tritangent circles and use the parametric form of the ellipses in order to design an exact subdivision-based algorithm, which is implemented on Maple. This approach essentially answers κ₄ as well. We conclude with current work on optimizing κ₃ and implementing it in C++.

References

[1]

H. Alt, O. Cheong, and A. Vigneron. The Voronoi Diagram of Curved Objects. Discrete and Computational Geometry, 34(3):439--453, Sep 2005.]]

Digital Library

[2]

P. Angelier and M. Pocchiola. A sum of squares theorem for visibility. In Procs of 17th SoCG, pages 302--311. ACM Press, 2001.]]

Digital Library

[3]

F. Anton. Voronoi diagrams of semi-algebraic sets. PhD thesis, The University of British Columbia, January 2004.]]

Digital Library

[4]

F. Anton, J.-D. Boissonnat, D. Mioc, and M. Yvinec. An exact predicate for the optimal construction of the additively weighted Voronoi diagram. Europ. Workshop Comput. Geom, 2002.]]

[5]

D. Attali and J.-D. Boissonnat. Complexity of the delaunay triangulation of points on polyhedral surfaces. Discr. & Comp. Geometry, 30(3):437--452, 2003.]]

Digital Library

[6]

I. Boada, N. Coll, and J.A. Sellarès. Multiresolution approximations of generalized Voronoi diagrams. In Proc. Intern. Conf. Comp. Science, pages 98--106, 2004.]]

[7]

J.-D. Boissonnat and C. Delage. Convex hull and Voronoi diagram of additively weighted points. In Proc. 13th Annu. European Sympos. Algorithms, volume 3669 of Lecture Notes Comput. Sci, pages 367--378. Springer-Verlag, 2005.]]

Digital Library

[8]

J.-D. Boissonnat and M. Karavelas. On the combinatorial complexity of Euclidean Voronoi cells and convex hulls of d-dimensional spheres. In Proc. SODA, pages 305--312, 2003.]]

Digital Library

[9]

R. Brent. Algorithms for Minimization without Derivatives. Prentice-Hall, Englewood Cliffs, N.J., 1973.]]

[10]

C. Burnikel, S. Funke, K. Mehlhorn, S. Schirra, and S. Schmitt. A Separation Bound for Real Algebraic Expressions. In ESA, volume 2161 of LNCS, pages 254--265. Springer, 2001.]]

Digital Library

[11]

D. Cox, J. Little, and D. O'Shea. Using Algebraic Geometry. Number 185 in GTM. Springer, New York, 2nd edition, 2005.]]

[12]

I.Z. Emiris and M.I. Karavelas. The predicates of the Apollonius diagram: algorithmic analysis and implementation. Comp. Geom.: Theory & Appl., Spec. Issue on Robust Geometric Algorithms and their Implementations, 33(1-2):18--57, 2006.]]

[13]

I.Z. Emiris and E.P. Tsigaridas. Computing with real algebraic numbers of small degree. In Proc. ESA, LNCS, pages 652--663. Springer, 2004.]]

[14]

I.Z. Emiris and E.P. Tsigaridas. Real solving of bivariate polynomial systems. In V.G. Ganzha, E.W. Mayr, and E.V. Vorozhtsov, editors, Proc. Computer Algebra in Scientific Computing (CASC), LNCS, pages 150--161. Springer Verlag, 2005.]]

Digital Library

[15]

I.Z. Emiris and G.M. Tzoumas. Algebraic study of the Apollonius circle of three ellipses. In Proc. Europ. Works. Comp. Geom, pages 147--150, Holland, 2005. Also: Poster session, CASC'05, Greece. To appear in SIGSAM Bulletin.]]

[16]

F. Etayo, L. Gonzalez-Vega, and N. del Rio. A new approach to characterizing the relative position of two ellipses depending on one parameter. Comp.-Aided Geom. Design, 2005.]]

Digital Library

[17]

L. Habert. Computing bitangents for ellipses. In Proc. 17th Canad. Conf. Comp. Geom, pages 294--297, 2005.]]

[18]

I. Hanniel, R. Muthuganapathy, G. Elber, and M.-S. Kim. Precise Voronoi cell extraction of free-form rational planar closed curves. In Proc. 2005 ACM Symp. Solid and phys. modeling, pages 51--59 Cambridge, Massachusetts, 2005.]]

Digital Library

[19]

P. Harrington, C.O. Dúnlaing, and C. Yap. Optimal Voronoi diagram construction with n convex sites in three dimensions. Tech. Rep. TCDMATH 04-21, School of Mathematics, Dublin, 2004.]]

[20]

M.I. Karavelas and M. Yvinec. Voronoi diagram of convex objects in the plane. In Proc. ESA, pages 337--348, 2003.]]

[21]

D.-S. Kim, D. Kim, and K. Sugihara. Voronoi diagram of a circle set from Voronoi diagram of a point set: II. Geometry. CAGD, 18:563--585, 2001.]]

Digital Library

[22]

R. Klein, K. Mehlhorn, and S. Meiser. Randomised incremental construction of abstract Voronoi diagrams. Comput. Geom. Theory & Appl, 3(3):157--184, 1993.]]

Digital Library

[23]

M. McAllister, D. Kirkpatrick, and J. Snoeyink. A compact piecewise-linear Voronoi diagram for convex sites in the plane. Discrete Comput. Geom, 15:73--105, 1996.]]

Digital Library

[24]

B. Mourrain, J. P. Pavone, P. Trébuchet, and E. Tsigaridas. SYNAPS, a library for symbolic-numeric computation. In 8th Int. Symposium on Effective Methods in Algebraic Geometry, MEGA, Sardinia, Italy, May 2005. to appear.]]

[25]

W. Wang, J. Wang, and M. Kim. An algebraic condition for the separation of two ellipsoids. Comp. Aided Geom. Design, 18:531--539, 2001.]]

Digital Library

[26]

C. Yap. On guaranteed accuracy computation. In F. Chen and D. Wang, editors, Geometric Computation, volume 11 of Lect. Notes Series Comp. World Scientific, 2004.]]

[27]

C.K. Yap. Fundamental Problems of Algorithmic Algebra. Oxford University Press, New York, 2000.]]

Digital Library

Cited By

Lee MSugihara KKim D(2022)Robust Construction of Voronoi Diagrams of Spherical Balls in Three-Dimensional SpaceComputer-Aided Design10.1016/j.cad.2022.103374152(103374)Online publication date: Nov-2022
https://doi.org/10.1016/j.cad.2022.103374
Shah KSchwager M(2019)GRAPERobotics and Autonomous Systems10.1016/j.robot.2019.07.016121:COnline publication date: 1-Nov-2019
https://dl.acm.org/doi/10.1016/j.robot.2019.07.016
Yap CSharma VLien J(2012)Towards Exact Numerical Voronoi DiagramsProceedings of the 2012 Ninth International Symposium on Voronoi Diagrams in Science and Engineering10.1109/ISVD.2012.31(2-16)Online publication date: 27-Jun-2012
https://dl.acm.org/doi/10.1109/ISVD.2012.31
Show More Cited By

Index Terms

The predicates for the Voronoi diagram of ellipses
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

A real-time and exact implementation of the predicates for the Voronoi diagram of parametric ellipses
SPM '07: Proceedings of the 2007 ACM symposium on Solid and physical modeling

We study the Voronoi diagram, under the Euclidean metric, of a set of ellipses, given in parametric representation. We use an efficient incremental algorithm and focus on the required predicates. The paper concentrates on InCircle, which is the hardest ...
Exact Voronoi diagram of smooth convex pseudo-circles: General predicates, and implementation for ellipses

We examine the problem of computing exactly the Voronoi diagram (via the dual Delaunay graph) of a set of, possibly intersecting, smooth convex pseudo-circles in the Euclidean plane, given in parametric form. Pseudo-circles are (convex) sites, every ...
Voronoi diagram computations for planar NURBS curves
SPM '08: Proceedings of the 2008 ACM symposium on Solid and physical modeling

We present robust and efficient algorithms for computing Voronoi diagrams of planar freeform curves. Boundaries of the Voronoi diagram consist of portions of the bisector curves between pairs of planar curves. Our scheme is based on computing critical ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry

June 2006

500 pages

ISBN:1595933409

DOI:10.1145/1137856

Program Chairs:
Nina Amenta
University of California at Davis
,
Otfried Cheong
Korea Advanced Institute of Science and Technology

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SoCG06

Sponsor:

SoCG06: 22nd Annual Symposium on Computational Geometry

June 5 - 7, 2006

Arizona, Sedona, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
440
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lee MSugihara KKim D(2022)Robust Construction of Voronoi Diagrams of Spherical Balls in Three-Dimensional SpaceComputer-Aided Design10.1016/j.cad.2022.103374152(103374)Online publication date: Nov-2022
https://doi.org/10.1016/j.cad.2022.103374
Shah KSchwager M(2019)GRAPERobotics and Autonomous Systems10.1016/j.robot.2019.07.016121:COnline publication date: 1-Nov-2019
https://dl.acm.org/doi/10.1016/j.robot.2019.07.016
Yap CSharma VLien J(2012)Towards Exact Numerical Voronoi DiagramsProceedings of the 2012 Ninth International Symposium on Voronoi Diagrams in Science and Engineering10.1109/ISVD.2012.31(2-16)Online publication date: 27-Jun-2012
https://dl.acm.org/doi/10.1109/ISVD.2012.31
Hemmer MSetter OHalperin D(2010)Constructing the exact Voronoi diagram of arbitrary lines in three-dimensional space with fast point-locationProceedings of the 18th annual European conference on Algorithms: Part I10.5555/1888935.1888980(398-409)Online publication date: 6-Sep-2010
https://dl.acm.org/doi/10.5555/1888935.1888980
Aichholzer OAigner WAurenhammer FHackl TJüttler BPilgerstorfer ERabl M(2010)Divide-and-conquer for Voronoi diagrams revisitedComputational Geometry: Theory and Applications10.1016/j.comgeo.2010.04.00443:8(688-699)Online publication date: 1-Oct-2010
https://dl.acm.org/doi/10.1016/j.comgeo.2010.04.004
Aichholzer OAigner WAurenhammer FHackl TJüttler BPilgerstorfer ERabl MHershberger JFogel E(2009)Divide-and-conquer for Voronoi diagrams revisitedProceedings of the twenty-fifth annual symposium on Computational geometry10.1145/1542362.1542401(189-197)Online publication date: 8-Jun-2009
https://dl.acm.org/doi/10.1145/1542362.1542401
Hanniel IElber G(2009)Computing the Voronoi cells of planes, spheres and cylinders in R3Computer Aided Geometric Design10.1016/j.cagd.2008.09.01026:6(695-710)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.1016/j.cagd.2008.09.010
Hanniel IElber GHaines EMcGuire M(2008)Computing the Voronoi cells of planes, spheres and cylinders in R3Proceedings of the 2008 ACM symposium on Solid and physical modeling10.1145/1364901.1364911(47-58)Online publication date: 2-Jun-2008
https://dl.acm.org/doi/10.1145/1364901.1364911
Emiris ITsigaridas E(2008)Real algebraic numbers and polynomial systems of small degreeTheoretical Computer Science10.1016/j.tcs.2008.09.009409:2(186-199)Online publication date: 10-Dec-2008
https://dl.acm.org/doi/10.1016/j.tcs.2008.09.009
Tsigaridas EEmiris I(2008)On the complexity of real root isolation using continued fractionsTheoretical Computer Science10.1016/j.tcs.2007.10.010392:1-3(158-173)Online publication date: 20-Feb-2008
https://dl.acm.org/doi/10.1016/j.tcs.2007.10.010
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten