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.
%0 Journal Article
%1 rbkmsw-dbir-08
%A Reinbacher, Iris
%A Benkert, Marc
%A van Kreveld, Marc
%A Mitchell, Joseph S.B.
%A Snoeyink, Jack
%A Wolff, Alexander
%D 2008
%J Algorithmica
%K GIS imprecise_regions minimum_perimeter_polygon myown red-blue_separation
%N 3
%P 386--414
%R 10.1007/s00453-007-9042-5
%T Delineating Boundaries for Imprecise Regions
%V 50
%X 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.
@article{rbkmsw-dbir-08,
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.},
added-at = {2024-07-14T10:03:47.000+0200},
author = {Reinbacher, Iris and Benkert, Marc and van Kreveld, Marc and Mitchell, Joseph S.B. and Snoeyink, Jack and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/20548c42b7d7b826410d648ad5f7f2235/awolff},
doi = {10.1007/s00453-007-9042-5},
interhash = {61832d5d11ed73a910eb53cff7651be3},
intrahash = {0548c42b7d7b826410d648ad5f7f2235},
journal = {Algorithmica},
keywords = {GIS imprecise_regions minimum_perimeter_polygon myown red-blue_separation},
number = 3,
pages = {386--414},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/rbkmsw-dbir-07.pdf},
succeeds = {rbkmw-dbir-05},
timestamp = {2024-07-14T10:03:47.000+0200},
title = {Delineating Boundaries for Imprecise Regions},
volume = 50,
year = 2008
}