AN OPTIMAL ALGORITHM FOR REALIZING A DELAUNAY TRIANGULATION

Authors
LAMBERT T
Citation
T. Lambert, AN OPTIMAL ALGORITHM FOR REALIZING A DELAUNAY TRIANGULATION, Information processing letters, 62(5), 1997, pp. 245-250
Citations number
14
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
62
Issue
5
Year of publication
1997
Pages
245 - 250
Database
ISI
SICI code
0020-0190(1997)62:5<245:AOAFRA>2.0.ZU;2-Z
Abstract
Dillencourt (1990) gives a constructive proof for the realizability as a Delaunay triangulation of any triangulation of the interior of a si mple polygon A naive implementation of the construction will take O(n( 2)) time. I give a simple O(n) algorithm for this problem. An applicat ion of this algorithm is generating test data for algorithms that proc ess convex polygons. (C) 1997 Elsevier Science B.V.