Preprocessing imprecise points for Delaunay triangulation: Simplified and extended

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

Research output: Contribution to journalArticleAcademicpeer-review

18 Citations (Scopus)
95 Downloads (Pure)

Abstract

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
JournalAlgorithmica
Volume61
Issue number3
DOIs
Publication statusPublished - 2011

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

  • Cite this