Delineating Boundaries for Imprecise Regions
Algorithmica, 50 (3):
386--414 (2008)DOI: 10.1007/s00453-007-9042-5
Abstract
In geographic information retrieval, queries often
utilize names of geographic regions that do not have
a well-defined boundary, such as ``Southern
France.'' We provide two classes of algorithms for
the problem of computing reasonable boundaries of
such regions, based on evidence of given data points
that are deemed likely to lie either inside or
outside the region. Our problem formulation leads to
a number of problems related to red-blue point
separation and minimum-perimeter polygons, many of
which we solve algorithmically. We give experimental
results from our implementation and a comparison of
the two approaches.
