Preprocessing imprecise points for Delaunay triangulation: Simplified and extended

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

Research output: Contribution to journalArticleAcademicpeer-review

31 Citations (Scopus)
154 Downloads (Pure)


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, 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, e.g., overlapping disks of different sizes and fat regions. Keywords: Delaunay triangulation - Data imprecision - Quadtree.
Original languageEnglish
Pages (from-to)674-693
Issue number3
Publication statusPublished - 2011


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

Cite this