U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

PUBLICATIONS

Computing Delaunay triangulations for comet-shaped polygons

Published

Author(s)

Javier Bernal

Abstract

In this paper, we present two triangulation algorithms which combined produce an algorithm for computing Delaunay triangulations for comet-shaped polygons. The first algorithm constructs in linear time a triangulation for a comet-shaped polygon. The second algorithm constructs a Delaunay triangulation for a polygon from any triangulation for the polygon. The algorithms can be used for deleting vertices in a Delaunay triangulation and for computing constrained Delaunay triangulations.
Citation
NIST Interagency/Internal Report (NISTIR) - 4716
Report Number
4716
NIST Pub Series
NIST Interagency/Internal Report (NISTIR)
Pub Type
NIST Pubs

Download Paper

DOI Link

Keywords

algorithm, comet-shaped polygon, computational complexity, computational geometry, constrained Delaunay triangulation, Voronoi diagram

Citation

Bernal, J. (1991), Computing Delaunay triangulations for comet-shaped polygons, NIST Interagency/Internal Report (NISTIR), National Institute of Standards and Technology, Gaithersburg, MD, [online], https://doi.org/10.6028/NIST.IR.4716 (Accessed December 13, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created November 1, 1991, Updated November 10, 2018