%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 Red-BlueSeparation ImpreciseRegions MinimumPerimeterPolygons GIS %N 3 %P 386--414 %R 10.1007/s00453-007-9042-5 %T Delineating Boundaries for Imprecise Regions %U http://dx.doi.org/10.1007/s00453-007-9042-5 %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 = {2010-04-13T09:41:28.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/fink}, doi = {10.1007/s00453-007-9042-5}, interhash = {61832d5d11ed73a910eb53cff7651be3}, intrahash = {0548c42b7d7b826410d648ad5f7f2235}, journal = {Algorithmica}, keywords = {Red-BlueSeparation ImpreciseRegions MinimumPerimeterPolygons GIS}, number = 3, pages = {386--414}, pdf = {#AWPUBURL#rbkmsw-dbir-07.pdf}, succeeds = {rbkmw-dbir-05}, timestamp = {2010-04-13T09:41:28.000+0200}, title = {Delineating Boundaries for Imprecise Regions}, url = {http://dx.doi.org/10.1007/s00453-007-9042-5}, volume = 50, year = 2008 }