Internal and external algorithms for the point-in-regions problem - the INSIDE join of georelational algebra

DOI10.1007/BF01840388MaRDI QIDQ1262147zbMATH OpenOpenAlexFDO

Authors Gabriele Blankenagel, Ralf Hartmut Gueting

Publication date 1990

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01840388

zbMATH Keywords

computational geometrydivide-and-conquergeometric databasegeorelational algebraplanar subdivisionsplane-sweeppoint location

Mathematics Subject Classification ID

Other problems of combinatorial convexity (52A37) Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99) Artificial intelligence (68T99) Computing methodologies and applications (68U99) Algorithms in computer science (68W99)

Review text

The authors deal with location problems (where preprocessing is not allowed) arising in computational geometry. The problem is attacked from various viewpoints and in overall summary it represents an interesting contribution with application namely in geometric database systems. Powerful divide-and-conquer and plane-sweep techniques are tailor-made, generalized and compared. Internal versions (relying on internal memory only), internal versions running in sublinear space, as well as external versions (that uses only constant amount of internal memory) of algorithms are also discussed. The paper is well-written.

Recommendations

• scientific article; zbMATH DE number 4082961
• scientific article; zbMATH DE number 1182923
• scientific article; zbMATH DE number 1303612
• Does a point lie inside a polygon ?
• Planar point location for large data sets

Cites work

• A new approach to rectangle intersections
• A Note on Locating a Set of Points in a Planar Subdivision
• A practical divide-and-conquer algorithm for the rectangle intersection problem
• Divide-and-conquer in planar geometry
• Finding Rectangle Intersections by Divide-and-Conquer
• scientific article; zbMATH DE number 3887061 (Why is no real title available?)
• scientific article; zbMATH DE number 4080979 (Why is no real title available?)
• scientific article; zbMATH DE number 3653523 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles
• Optimal Point Location in a Monotone Subdivision
• Optimal Search in Planar Subdivisions
• Organization and maintenance of large ordered indexes
• Searching and storing similar lists
• The measure problem for rectangular ranges in d-space
• Topologically sweeping an arrangement

Cited in

(2)

• A simple but effective improvement to the plumb-line algorithm
• scientific article; zbMATH DE number 4082961 (Why is no real title available?)

This page was built for publication: Internal and external algorithms for the point-in-regions problem - the INSIDE join of georelational algebra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1262147)