A NOTE ON DELAUNAY DIAGONAL FLIPS

Authors
FORTUNE S
Citation
S. Fortune, A NOTE ON DELAUNAY DIAGONAL FLIPS, Pattern recognition letters, 14(9), 1993, pp. 723-726
Citations number
10
Categorie Soggetti
Computer Sciences, Special Topics","Computer Applications & Cybernetics
Journal title
Pattern recognition letters → ACNP
ISSN journal
01678655
Volume
14
Issue
9
Year of publication
1993
Pages
723 - 726
Database
ISI
SICI code
0167-8655(1993)14:9<723:ANODDF>2.0.ZU;2-3
Abstract
Suppose we wish to transform an arbitrary triangulation of a point set into its Delaunay triangulation. A Delaunay diagonal flip replaces th e common edge of two abutting triangles with the opposite diagonal if the resulting triangles would locally satisfy the Delaunay empty-circl e condition. We show that THETA(n2) Delaunay diagonal flips are necess ary and sufficient to transform any triangulation into the Delaunay tr iangulation.