The Approximation of Two-Dimensional Spatial Objects by Two Bounding Rectangles

Minimal bounding rectangles are a simple and efficient tool for approximating geometries, particularly for accelerating spatial queries. If a spatial object fills a rectangular shape to a certain extent, then the minimal bounding rectangle is a reasonable approximation. Unfortunately some geo object...

Full description

Saved in:
Bibliographic Details
Published in:Spatial cognition and computation 2011-05, Vol.11 (2), p.129-152
Main Author: Roth, Jörg
Format: Article
Language:English
Subjects:
Algorithms
Approximation
bounding box
geometric approximation
Mathematical analysis
Queries
Rectangles
Rivers
spatial data
spatial indexing
Two dimensional
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:Minimal bounding rectangles are a simple and efficient tool for approximating geometries, particularly for accelerating spatial queries. If a spatial object fills a rectangular shape to a certain extent, then the minimal bounding rectangle is a reasonable approximation. Unfortunately some geo objects, such as streets or rivers, have a small area but large bounding rectangles. In this paper we suggest an approximation with two bounding rectangles instead of a single one. Since the corresponding shape provides a better approximation, we get a greater average benefit. We present an efficient algorithm that computes the two rectangles with the theoretically smallest combined area that encloses a given geometry in O(n · log n) steps. Following a detailed description of the algorithm, we present an analysis with approximately 4 million real geo objects.
ISSN:1387-5868
1542-7633
DOI:10.1080/13875868.2010.512673