Please use this identifier to cite or link to this item:
Title: I/O-efficient algorithm for constrained Delaunay triangulation with applications to proximity search
Authors: WU XINYU
Keywords: constrained delaunay triangulation proximity external memory
Issue Date: 24-Mar-2005
Citation: WU XINYU (2005-03-24). I/O-efficient algorithm for constrained Delaunay triangulation with applications to proximity search. ScholarBank@NUS Repository.
Abstract: Delaunay Triangulation (DT) and its extension Constrained Delaunay Triangulation (CDT) are spatial data structures that have wide applications in spatial data processing. Our recent survey, however, shows that there is a surprising lack of I/O-efficient algorithms for computing DT/CDT on large spatial databases. In view of this, we propose an external-memory algorithm for computing CDT on spatial databases with DT being computed as a special instances.Our proposal is based on the divide and conquer paradigm which compute DT/CDT of in-memory partitions before merging them into the final result. This is made possible by discovering mathematical properties that precisely characterize the set of triangles that are involved in the merging step. Extensive experiments show that our algorithm outperforms another provably good external-memory algorithm by roughly an order of magnitude when computing DT. For CDT, which has no known external-memory algorithm, we show experimentally that our algorithm scale up well for large databases with size in the range of gigabytes.Obstructed proximity search has recently attracted much attention from the spatial database community due to its wide applications. One main difficulty for processing obstructed proximity search queries lies in how to prune irrelevant data effectively to limit the search space. The performance of the existing pruning strategies is unsatisfactory for many applications. We propose a novel solution based on the spanner graph property of the CDT to address this key weakness. In particular, we show how our pruning strategy can be used to process the obstructed $k$-nearest-neighbors and range queries.
Appears in Collections:Master's Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
report.pdf2.93 MBAdobe PDF



Page view(s)

checked on Oct 28, 2018


checked on Oct 28, 2018

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.