Preprocessing Imprecise Points for Delaunay Triangulation: Simplified and Extended

摘要

Suppose we want to compute the Delaunay triangulation of a set P whose points are restricted to a collection TZ of input regions known in advance. Building on recent work by Loffler and Snoeyink, we show how to leverage our knowledge of TZ 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.