Affordable Access

Delineating imprecise regions via shortest-path graphs

Publication Date
  • Computer Science


Delineating Imprecise Regions via Shortest-Path Graphs∗ Mark de Berg [email protected] Wouter Meulemans [email protected] Bettina Speckmann [email protected] Dep. of Mathematics and Computer Science, TU Eindhoven, The Netherlands ABSTRACT An imprecise region, also called a vernacular region, is a region without a precise or administrative boundary. We present a new method to delineate imprecise regions from a set of points that are likely to lie inside the region. We use shortest-path graphs based on the squared Euclidean distance which capture the shape of region boundaries well. Shortest-path graphs naturally adapt to point sets of vary- ing density, and they are always connected. As opposed to neighborhood graphs, they use a non-local criterion to determine which points to connect. Furthermore, shortest- path graphs can easily be extended to take geographic con- text into account by modeling context as “soft” obstacles. We present efficient algorithms to compute shortest-path graphs with or without geographic context. We experimen- tally evaluate the quality of the imprecise regions computed with our method. To fairly compare our results to those ob- tained by the common KDE approach, we also show how to integrate context into KDE by again using soft obstacles. Categories and Subject Descriptors I.5.1 [Pattern Recognition]: Models—Geometric; H.2.8 [Database Management]: Database Applications—Spa- tial Databases and GIS ; I.3.5 [Computer Graphics]: Com- putational Geometry and Object Modeling General Terms Algorithms, Theory Keywords Vernacular regions, Shortest-path graph, Geographic con- text ∗W. Meulemans and B. Speckmann are supported by the Netherlands Organisation for Scientific Research (NWO) un- der project no. 639.022.707. This paper is based on the Master’s thesis [18] of the second author. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distribute

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times