More Web Proxy on the site http://driver.im/

research-article

Exact Delaunay graph of smooth convex pseudo-circles: general predicates, and implementation for ellipses

Authors:

Ioannis Z. Emiris,

Elias P. Tsigaridas,

George M. TzoumasAuthors Info & Claims

SPM '09: 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling

Pages 211 - 222

https://doi.org/10.1145/1629255.1629282

Published: 05 October 2009 Publication History

Abstract

We examine the problem of computing exactly the Delaunay graph (and the dual Voronoi diagram) of a set of, possibly intersecting, smooth convex pseudo-circles in the Euclidean plane, given in parametric form. Pseudo-circles are (convex) sites, every pair of which has at most two intersecting points. The Delaunay graph is constructed incrementally. Our first contribution is to propose robust end efficient algorithms for all required predicates, thus generalizing our earlier algorithms for ellipses, and we analyze their algebraic complexity, under the exact computation paradigm. Second, we focus on InCircle, which is the hardest predicate, and express it by a simple sparse 5 X 5 polynomial system, which allows for an efficient implementation by means of successive Sylvester resultants and a new factorization lemma. The third contribution is our cgal-based c++ software for the case of ellipses, which is the first exact implementation for the problem. Our code spends about 98 sec to construct the Delaunay graph of 128 non-intersecting ellipses, when few degeneracies occur. It is faster than the cgal segment Delaunay graph, when ellipses are approximated by k-gons for k > 15.

References

[1]

O. Aichholzer, W. Aigner, F. Aurenhammer, T. Hackl, B. Jüttler, and M. Rabl. Medial axis computation for planar free-form shapes. Comp. Aided Design, (to appear), 2009.

Digital Library

[2]

H. Alt, O. Cheong, and A. Vigneron. The Voronoi diagram of curved objects. Discr. and Comput. Geometry, 34(3):439--453, 2005.

Digital Library

[3]

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

Digital Library

[4]

CGAL: Computational geometry algorithms library. http://www.cgal.org.

[5]

J. J. Chou. Voronoi diagrams for planar shapes. IEEE Comput. Graph. Appl., 15(2):52--59, 1995.

Digital Library

[6]

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

[7]

D. I. Diochnos, I. Z. Emiris, and E. P. Tsigaridas. On the asymptotic and practical complexity of solving bivariate systems over the reals. J. Symbolic Computation, (to appear), 2009.

Digital Library

[8]

G. Elber, M.-S. Kim, and H.-S. Heo. The convex hull of rational plane curves. Graph. Models, 63(3):151--162, 2001.

Digital Library

[9]

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

[10]

I. Z. Emiris, B. Mourrain, and E. P. Tsigaridas. Real algebraic numbers: complexity analysis and experimentation. In P. Hertling, C. Hoffmann, W. Luther, and N. Revol, editors, Reliable Implementations of Real Number Algorithms: Theory and Practice, volume 5045 of LNCS, pages 57--82. Springer Verlag, 2008.

Digital Library

[11]

I. Z. Emiris, E. P. Tsigaridas, and G. M. Tzoumas. Predicates for the exact Voronoi diagram of ellipses under the euclidean metric. Intern. J. Computational Geometry&Applications, 18(6):567--597, 2008. Spec. Issue on SoCG'06.

[12]

I. Z. Emiris and G. M. Tzoumas. Exact and efficient evaluation of the InCircle predicate for parametric ellipses and smooth convex objects. Comput. Aided Des., 40(6):691--700, 2008.

Digital Library

[13]

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

[14]

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

Digital Library

[15]

M. Held. Vroni: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments. Comput. Geom. Theory Appl., 18:95--123, 2001.

Digital Library

[16]

M. Held and S. Huber. Topology-oriented incremental computation of Voronoi diagrams of circular arcs and straight line-segments. Comp. Aided Design, (to appear), 2009. Spec. issue on Voronoi diagrams.

Digital Library

[17]

M. I. Karavelas. A robust and efficient implementation for the segment Voronoi diagram. In Proc. Int. Symp. Voronoi Diagrams, pages 51--62, 2004.

[18]

M. I. Karavelas and M. Yvinec. Voronoi diagram of convex objects in the plane. In Proc. Europ. Symp. Algorithms, LNCS, pages 337--348. Springer, 2003.

[19]

D.-S. Kim, D. Kim, and K. Sugihara. Voronoi diagram of a circle set from Voronoi diagram of a point set: II. Geometry. Comp. Aid. Geom. Des., 18(6):563--585, 2001.

Digital Library

[20]

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

[21]

R. Ramamurthy and R. Farouki. Voronoi diagram and medial axis algorithm for planar domains with curved boundaries - II: detailed algorithm description. J. Comput. Appl. Math., 102(2):253--277, 1999.

Digital Library

[22]

R. Ramamurthy and R. Farouki. Voronoi diagram and medial axis algorithm for planar domains with curved boundaries I. theoretical foundations. J. Comput. Appl. Math., 102(1):119--141, 1999.

Digital Library

[23]

M. Ramanathan and B. Gurumoorthy. Constructing medial axis transform of planar domains with curved boundaries. Comp.-Aided Design, 35(7):619--632, 2003.

[24]

J.-K. Seong, E. Cohen, and G. Elber. Voronoi diagram computations for planar nurbs curves. In Proc. ACM Symp. Solid&Phys. modeling, pages 67--77, NY, 2008.

Digital Library

Cited By

Adamou IMourrain B(2021)Computing the Topology of Voronoï Diagrams of Parallel Half-LinesMathematics in Computer Science10.1007/s11786-021-00508-115:4(859-876)Online publication date: 12-Apr-2021
https://doi.org/10.1007/s11786-021-00508-1
Sundar BMukundan MMuthuganapathy R(2020)A unified approach towards computing Voronoi diagram, medial axis, Delaunay graph and α-hull of planar closed curves using touching discsComputers & Graphics10.1016/j.cag.2020.05.01089(131-143)Online publication date: Jun-2020
https://doi.org/10.1016/j.cag.2020.05.010
Venkataraman VMuthuganapathy R(2015)Algorithm for computing positive α-hull for a set of planar closed curvesComputers and Graphics10.1016/j.cag.2015.05.01851:C(125-135)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1016/j.cag.2015.05.018
Show More Cited By

Recommendations

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 ...
Separation by Convex Pseudo-Circles
SOCG'14: Proceedings of the thirtieth annual symposium on Computational geometry

Let S be a finite set of n points in the plane in general position. We prove that every inclusion-maximal family of subsets of S separable by convex pseudo-circles has the same cardinal (n 0)+(n 1)+(n 2)+(n 3). This number does not depend on the ...
Delaunay Triangular Meshes in Convex Polygons

An algorithm for producing a triangular mesh in a convex polygon is presented. It is used in a method for the finite element triangulation of a complex polygonal region of the plane in which the region is decomposed into convex polygons. The interior ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SPM '09: 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling

October 2009

380 pages

ISBN:9781605587110

DOI:10.1145/1629255

Conference Chair:
Wim Bronsvoort
Delft University of Technology, The Netherlands
,
General Chairs:
Daniel Gonsor
The Boeing Company
,
William Regli
Drexel University
,
Thomas Grandine
The Boeing Company
,
Jan Vandenbrande
The Boeing Company
,
Program Chairs:
Jens Gravesen
Technical University of Denmark, Denmark
,
John Keyser
Texas A&M University

Copyright © 2009 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

SIAM Activity Group on Geometric Design

In-Cooperation

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 October 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

State Scholarship Foundation of Greece
Sixth Framework Programme
Seventh Framework Programme

Conference

SIAM '09

Sponsor:

SIAM '09: 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling

October 5 - 8, 2009

California, San Francisco

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
140
Total Downloads

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

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Adamou IMourrain B(2021)Computing the Topology of Voronoï Diagrams of Parallel Half-LinesMathematics in Computer Science10.1007/s11786-021-00508-115:4(859-876)Online publication date: 12-Apr-2021
https://doi.org/10.1007/s11786-021-00508-1
Sundar BMukundan MMuthuganapathy R(2020)A unified approach towards computing Voronoi diagram, medial axis, Delaunay graph and α-hull of planar closed curves using touching discsComputers & Graphics10.1016/j.cag.2020.05.01089(131-143)Online publication date: Jun-2020
https://doi.org/10.1016/j.cag.2020.05.010
Venkataraman VMuthuganapathy R(2015)Algorithm for computing positive α-hull for a set of planar closed curvesComputers and Graphics10.1016/j.cag.2015.05.01851:C(125-135)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1016/j.cag.2015.05.018
Vishwanath ARamanathan M(2013)Determining Curves in Convex Hull from a Set of Planar Closed Convex CurvesComputer-Aided Design and Applications10.1080/16864360.2013.83414811:1(99-106)Online publication date: 24-Sep-2013
https://doi.org/10.1080/16864360.2013.834148
Vishwanath AArun Srivatsan RRamanathan M(2013)Minimum area enclosure and alpha hull of a set of freeform planar closed curvesComputer-Aided Design10.1016/j.cad.2012.12.00145:3(751-763)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1016/j.cad.2012.12.001
Emiris IMantzaflaris AMourrain BOssowski SLecca P(2012)Yet another algorithm for generalized Voronoï DiagramsProceedings of the 27th Annual ACM Symposium on Applied Computing10.1145/2245276.2245299(109-110)Online publication date: 26-Mar-2012
https://dl.acm.org/doi/10.1145/2245276.2245299
Aichholzer OAigner WHackl TWolpert N(2010)Exact medial axis computation for circular arc boundariesProceedings of the 7th international conference on Curves and Surfaces10.1007/978-3-642-27413-8_2(28-42)Online publication date: 24-Jun-2010
https://dl.acm.org/doi/10.1007/978-3-642-27413-8_2
Mantzaflaris AMourrain B(2010)A subdivision approach to planar semi-algebraic setsProceedings of the 6th international conference on Advances in Geometric Modeling and Processing10.1007/978-3-642-13411-1_8(104-123)Online publication date: 16-Jun-2010
https://dl.acm.org/doi/10.1007/978-3-642-13411-1_8

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.

Media

Figures

Other

Tables

View Table of Contents