Abstract
In some applications of triangulation, such as finite-element mesh generation, the aim is to triangulate a given domain, not just a set of points. One approach to meeting this requirement, while maintaining the desirable properties of Delaunay triangulation, has been to enforce the empty circumcircle property of Delaunay triangulation, subject to the additional constraint that the edges of a polygon be covered by edges of the triangulation. In finite-element mesh generation it is usually necessary to include additional points besides the vertices of the domain boundary. This motivates us to ask whether it is possible to trinagulate a domain by introducing additional points in such a manner that the Delaunay triangulation of the points includes the edges of the domain boundary. We present algorithms that given a multiply connected polygonal domain withN vertices, placeK additional points on the boundary inO(N logN + K) time such that the polygon is covered by the edges of the Delaunay triangulation of theN + K points. Furthermore,K is the minimum number of additional points such that a circle, passing through the endpoints of each boundary edge segment, exists that does not contain in its interior any other part of the domain boundary. We also show that by adding only one more point per edge, certain degeneracies that may otherwise arise can be avoided.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. D. Boissonnat. Shape reconstruction from planar cross sections.Computer Vision, Graphics, and Image Processing,44(1): 1–29, October 1988.
F. L. Bookstein. The line-skeleton.Computer Graphics and Image Processing,11:123–137, October 1979.
L. P. Chew. Constrained Delaunay triangulations.Algorithmica,4:97–108, 1989.
H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin, 1987.
S. Fortune. A sweepline algorithm for Voronoi diagrams.Algorithmica,2(2): 153–174, 1987.
O. D. Faugeras, E. Le Bras-Mehlman, and J. D. Boissonnat. Representing stereo data with the Delaunay triangulation.Artificial Intelligence,44(1–2):41–87, July 1990.
L. De Floriani, B. Falcidieno, and C. Pienovi. Delaunay-based representation of surfaces defined over arbitrarily shaped domains.Computer Vision, Graphics, and Image Processing,32:127–140, 1985.
L. Guibas and J. Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams.ACM Transactions on Graphics,4(2):74–123, 1985.
D. T. Lee and A. K. Lin. Generalized Delaunay triangulation for planar graphs.Discrete and Computational geometry,1:201–217, 1986.
L. R. Nackman and V. Srinivasan. Bisectors of linearly separable sets.Discrete and Computational Geometry,6:263–275, 1991.
R. Sedgewick.Algorithms, 2nd edn. Addison-Wesley, Reading, MA, 1988.
V. Srinivasan and L. R. Nackman. Maximal balls of linearly separable sets.International Journal of Computational Geometry and Applications, to appear.
N. Sapidis and R. Perucchio. Delaunay triangulation of arbitrarily shaped planar domains.Computer Aided Geometric Design,8:421–437, 1991.
Author information
Authors and Affiliations
Additional information
Communicated by Bernard Chazelle.
Rights and permissions
About this article
Cite this article
Nackman, L.R., Srinivasan, V. Point placement algorithms for Delaunay triangulation of polygonal domains. Algorithmica 12, 1–17 (1994). https://doi.org/10.1007/BF01377180
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01377180