Cited By
View all- Adamou IMourrain B(2021)Computing the Topology of Voronoï Diagrams of Parallel Half-LinesMathematics in Computer Science10.1007/s11786-021-00508-1Online publication date: 12-Apr-2021
Yet another algorithm for generalized Voronoï Diagrams
Pages 109 - 110
Abstract
We design and implement an efficient algorithm for the computation of generalized Voronoï Diagrams (VD's) constrained to a given domain. Our framework is general and applicable to any VD-type where the distance field is given by a polynomial. We use the Bernstein form of polynomials to subdivide the domain and isolate bisector domains or domains that contain a Voronoï vertex. Efficiency is due to a filtering process, based on bounding the distance functions over the subdivided domains. The output is a polygonal description of each Voronoï cell up to any user-defined precision.
References
[1]
O. Aichholzer, W. Aigner, F. Aurenhammer, T. Hackl, B. Jüttler, E. Pilgerstorfer, and M. Rabl. Divide-and-conquer algorithms for Voronoï diagrams revisited. Comput. Geom. Theory Appl., 43: 688--699, 2010.
[2]
H. Edelsbrunner and R. Seidel. Voronoï diagrams and arrangements. Discr. and Compt. Geom., 1: 25--44, 1986.
[3]
I. Z. Emiris, E. P. Tsigaridas, and G. M. Tzoumas. Exact Delaunay graph of smooth convex pseudo-circles: general predicates, and implementation for ellipses. In SPM '09, p. 211--222, NY, USA, 2009. ACM.
[4]
G. Farin. Curves and surfaces for CAGD: a practical guide. Morgan Kaufmann Publishers Inc., SF, CA, USA, 2002.
[5]
F. Labelle and J. R. Shewchuk. Anisotropic Voronoï diagrams and guaranteed-quality anisotropic mesh generation. In SCG '03, p. 191--200, NY, USA, 2003. ACM.
[6]
A. Mantzaflaris and B. Mourrain. A subdivision approach to planar semi-algebraic sets. In Geometric Modeling and Processing, vol. 6130 of LNCS, p. 104--123. Springer, 2010.
[7]
B. Mourrain and J. Pavone. Subdivision methods for solving polynomial equations. JSC, 44(3): 292--306, 2009.
Index Terms
- Yet another algorithm for generalized Voronoï Diagrams
Recommendations
Technical note: Voronoi diagrams of algebraic distance fields
We design and implement an efficient and certified algorithm for the computation of Voronoi diagrams (VDs) constrained to a given domain. Our framework is general and applicable to any VD-type where the distance field is given explicitly or implicitly ...
Yet another hexahedral dominant meshing algorithm
In this paper, we describe a robust meshing algorithm for obtaining a mixed mesh with large number of hexahedral/prismatic elements grown over the domain boundary respecting the user imposed anisotropic metric where physics matter the most and in areas ...
Generic Remeshing of 3D Triangular Meshes with Metric-Dependent Discrete Voronoi Diagrams
In this paper, we propose a generic framework for 3D surface remeshing. Based on a metric-driven Discrete Voronoi Diagram construction, our output is an optimized 3D triangular mesh with a user defined vertex budget. Our approach can deal with a wide ...
Comments
Information & Contributors
Information
Published In
March 2012
2179 pages
Copyright © 2012 Authors.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 26 March 2012
Check for updates
Author Tags
Qualifiers
- Poster
Conference
SAC 2012
Sponsor:
Acceptance Rates
SAC '12 Paper Acceptance Rate 270 of 1,056 submissions, 26%;
Overall Acceptance Rate 1,650 of 6,669 submissions, 25%
Upcoming Conference
SAC '25
- Sponsor:
- sigapp
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 107Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 01 Mar 2025
Other Metrics
Citations
Cited By
View all- Adamou IMourrain B(2021)Computing the Topology of Voronoï Diagrams of Parallel Half-LinesMathematics in Computer Science10.1007/s11786-021-00508-1Online publication date: 12-Apr-2021
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in