Delineating boundaries for imprecise regions

Iris Reinbacher; Marc Benkert; Marc Van Kreveld; Joseph S.B. Mitchell; Alexander Wolff

doi:10.1007/11561071_15

Delineating boundaries for imprecise regions

Iris Reinbacher
, Marc Benkert
, Marc Van Kreveld
, Joseph S.B. Mitchell
, Alexander Wolff

Applied Mathematics and Statistics

Utrecht University
Karlsruhe Institute of Technology

Research output: Contribution to journal › Conference article › peer-review

8 Scopus citations

Abstract

In geographic information retrieval, queries often use 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.

Original language	English
Pages (from-to)	143-154
Number of pages	12
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3669
DOIs	https://doi.org/10.1007/11561071_15
State	Published - 2005
Event	13th Annual European Symposium on Algorithms, ESA 2005 - Palma de Mallorca, Spain Duration: Oct 3 2005 → Oct 6 2005

Access to Document

10.1007/11561071_15

Cite this

@article{ab98de30bf3e44cc856bce3cead5d513,

title = "Delineating boundaries for imprecise regions",

abstract = "In geographic information retrieval, queries often use 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.",

author = "Iris Reinbacher and Marc Benkert and \{Van Kreveld\}, Marc and Mitchell, \{Joseph S.B.\} and Alexander Wolff",

year = "2005",

doi = "10.1007/11561071\_15",

language = "English",

volume = "3669",

pages = "143--154",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

note = "13th Annual European Symposium on Algorithms, ESA 2005 ; Conference date: 03-10-2005 Through 06-10-2005",

}

TY - JOUR

T1 - Delineating boundaries for imprecise regions

AU - Reinbacher, Iris

AU - Benkert, Marc

AU - Van Kreveld, Marc

AU - Mitchell, Joseph S.B.

AU - Wolff, Alexander

PY - 2005

Y1 - 2005

N2 - In geographic information retrieval, queries often use 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.

AB - In geographic information retrieval, queries often use 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.

UR - https://www.scopus.com/pages/publications/27144440506

U2 - 10.1007/11561071_15

DO - 10.1007/11561071_15

M3 - Conference article

AN - SCOPUS:27144440506

SN - 0302-9743

VL - 3669

SP - 143

EP - 154

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - 13th Annual European Symposium on Algorithms, ESA 2005

Y2 - 3 October 2005 through 6 October 2005

ER -

Delineating boundaries for imprecise regions

Abstract

Access to Document

Other files and links

Fingerprint

Cite this