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

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.