Delaunay triangulation of imprecise points simplified and extended

K. Buchin, M. Löffler, P. Morin, W. Mulzer

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)


Suppose we want to compute the Delaunay triangulation of a set P whose points are restricted to a collection R of input regions known in advance. Building on recent work by Löffler and Snoeyink[21], we show how to leverage our knowledge of R for faster Delaunay computation. Our approach needs no fancy machinery and optimally handles a wide variety of inputs, eg, overlapping disks of different sizes and fat regions.
Original languageEnglish
Title of host publicationAlgorithms and Data Structures (Proceedings 11th International Workshop, WADS 2009, Banff, Alberta, Canada, August 21-23, 2009)
EditorsF. Dehne, M. Gavrilova, J.-R. Sack, C.D. Tóth
Place of PublicationBerlin
ISBN (Print)978-3-642-03366-7
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Delaunay triangulation of imprecise points simplified and extended'. Together they form a unique fingerprint.

Cite this