Delineating Boundaries for Imprecise Regions |
| |
| Authors: | Iris Reinbacher Marc Benkert Marc van Kreveld Joseph S. B. Mitchell Jack Snoeyink Alexander Wolff |
| |
| Affiliation: | (1) Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Hong Kong, China;(2) Institute of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands;(3) Department of Computer Science, Karlsruhe University, Karlsruhe, Germany;(4) Department of Applied Mathematics and Statistics, State University of New York at Stony Brook, Stony Brook, USA;(5) Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, USA |
| |
| Abstract: | 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. This research is supported by the EU-IST Project No. IST-2001-35047 (SPIRIT) and by grant WO 758/4-2 of the German Research Foundation (DFG). |
| |
| Keywords: | Computational geometry Red-blue separation Imprecise regions |
| 本文献已被 SpringerLink 等数据库收录！ |
|
