Delineating Boundaries for Imprecise Regions

In geographic information retrieval, queries often name geographic regions that do not have a well-defined boundary, such as “Southern France.” We provide two algorithmic approaches to the problem of computing reasonable boundaries of such regions based on data points that have evidence indicating t...

Full description

Saved in:
Bibliographic Details
Published in:Algorithmica 2008-02, Vol.50 (3), p.386-414
Main Authors: Reinbacher, Iris, Benkert, Marc, van Kreveld, Marc, Mitchell, Joseph S. B., Snoeyink, Jack, Wolff, Alexander
Format: Article
Language:English
Subjects:
Algorithm Analysis and Problem Complexity
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Computer Science
Computer science
control theory
systems
Computer Systems Organization and Communication Networks
Data Structures and Information Theory
Exact sciences and technology
Information systems. Data bases
Mathematics of Computing
Memory organisation. Data processing
Software
Theoretical computing
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In geographic information retrieval, queries often name geographic regions that do not have a well-defined boundary, such as “Southern France.” We provide two algorithmic approaches to the problem of computing reasonable boundaries of such regions based on data points that have evidence indicating that they lie either inside or outside the region. Our problem formulation leads to a number of subproblems 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.
ISSN:0178-4617
1432-0541
DOI:10.1007/s00453-007-9042-5