Abstract
TheDelaunay diagram on a set of points in the plane, calledsites, is the straight-line dual graph of the Voronoi diagram. When no degeneracies are present, the Delaunay diagram is a triangulation of the sites, called theDelaunay triangulation. When degeneracies are present, edges must be added to the Delaunay diagram to obtain a Delaunay triangulation. In this paper we describe an optimalO(n logn) plane-sweep algorithm for computing a Delaunay triangulation on a possibly degenerate set of sites in the plane under theL 1 metric or theL ∞ metric.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J. Bentley. Programming pearls.Communications of ACM,28(3):245–250, March 1985.
M. W. Bern. Two probabilistic results on rectilinear Steiner trees. InProceedings of the 18th Annual ACM Symposium on the Theory of Computing, pages 433–441, May 1986.
L. P. Chew. There is a planer graph almost as good as the complete graph. InProceedings of the 2nd Annual Symposium on Computational Geometry, pages 169–177, 1986.
L. P. Chew and R. L. Drysdale. Voronoi diagrams based on convex distance functions. InProceedings of the Symposium on Computational Geometry, pages 235–244, 1985
R. A, Dwyer. A simple divide-and-conquer algorithm for constructing Delaunay triangulations inO(n log logn) expected time. InProceedings of the 2nd Annual Symposium on Computational Geometry, pages 276–284, 1986.
S. J. Fortune. A fast algorithm for polygon containment by translation. InAutomata, Languages, and Programming, 12th Colloquium, Lecture Notes in Computer Science, vol. 194, pages 189–198, Springer-Verlag, Berlin, 1985.
S. J. Fortune. A sweepline algorithm for Voronoi diagrams. InProceedings of the 2nd Annual Symposium on Computational Geometry, pages 313–319, 1986.
P. J. Green and R. Sibson. Computing Dirichlet tesselations in the plane.Computer Journal,21(22):73–87, 1981.
L. J. 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, April 1985.
F. K. Hwang. AnO(n logn) algorithm for rectilinear minimal spanning trees.Journal of the ACM,26(2):177–182, April 1979.
F. K. Hwang, AnO(n logn) algorithm for suboptimal rectilinear Steiner trees.IEEE Transactions on Circuits and Systems,26(1):75–77, January 1979.
D. T. Lee. Two-dimensional Voronoi diagrams in theL p -metric.Journal of the ACM,27(4):604–618, October 1980.
D. T. Lee. Relative neighborhood graphs in theL 1-metric.Pattern Recognition,18:327–332, 1985.
D. T. Lee and R. L. Drysdale, III. Generalization of Voronoi diagrams in the plane.SIAM Journal of Computing,10(1):73–87, February 1981.
D. T. Lee and B. J. Schachter. Two algorithms for constructing a Delaunay triangulation.International Journal of Computer and Information Sciences,9(3):219–242, 1980.
D. T. Lee and C. K. Wong. Voronoi diagrams inL 1 (L ∞) metrics with 2-dimensional storage applications.SIAM Journal of Computing,9:200–211, 1980.
J. H. Lee, N. K. Bose, and F. K. Hwang. Use of Steiner's problem in suboptimal routing in rectilinear metric.IEEE Transactions on Circuits and Systems,23(7):470–476, July 1976.
A. Lingas. The greedy and Delaunay triangulations are not bad in the average case.Information Processing Letters,22:25–31, 1986.
A. Maus. Delaunay triangulations and the convex hull ofn points in expected linear time.BIT,24:151–163, 1984.
F. P. Preparata and M. I. Shamos.Computational Geometry: An Introduction. Springer-Verlag, New York, 1985.
M. I. Shamos and D. Hoey. Closest point problems. InProceedings of the 16th IEEE Symposium on Foundations of Computer Science, pages 151–162, 1975.
J. M. Smith, D. T. Lee, and J. S. Liebman. AnO(n logn) heuristic algorithm for the rectilinear Steiner minimal tree problem.Engineering Optimization,4:179–192, 1980.
K. J. Supowit. The relative neighborhood graph, with an application to minimal spanning trees.Journal of the ACM,30(3):428–448, July 1983.
G. T. Toussaint. The relative neighbourhood graph of a finite planar set.Pattern Recognition,12:261–268, 1980.
Author information
Authors and Affiliations
Additional information
Communicated by Leonidas J. Guibas.
Supported by the National Science Foundation, through its Design, Tools and Test Program under Grant Number MIP 87-06139.
We are grateful to the two referees for their careful reading and helpful comments.
Rights and permissions
About this article
Cite this article
Shute, G.M., Deneen, L.L. & Thomborson, C.D. AnO(n logn) plane-sweep algorithm forL 1 andL ∞ Delaunay triangulations. Algorithmica 6, 207–221 (1991). https://doi.org/10.1007/BF01759042
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01759042