@article{4102, abstract = {Determining or counting geometric objects that intersect another geometric query object is at the core of algorithmic problems in a number of applied areas of computer science. This article presents a family of space-efficient data structures that realize sublinear query time for points, line segments, lines and polygons in the plane, and points, line segments, planes, and polyhedra in three dimensions.}, author = {Dobkin, David and Edelsbrunner, Herbert}, issn = {1090-2678}, journal = {Journal of Algorithms}, number = {3}, pages = {348 -- 361}, publisher = {Academic Press}, title = {{Space searching for intersecting objects}}, doi = {10.1016/0196-6774(87)90015-0}, volume = {8}, year = {1987}, } @article{4112, abstract = {The batched static version of a searching problem asks for performing a given set of queries on a given set of objects. All queries are known in advance. The batched dynamic version of a searching problem is the following: given a sequence of insertions, deletions, and queries, perform them on an initially empty set. We will develop methods for solving batched static and batched dynamic versions of searching problems which are in particular applicable to decomposable searching problems. The techniques show that batched static (dynamic) versions of searching problems can often be solved more efficiently than by using known static (dynamic) data structures. In particular, a technique called “streaming” is described that reduces the space requirements considerably. The methods have also a number of applications on set problems. E.g., the k intersecting pairs in a set of n axis-parallel hyper-rectangles in d dimensions can be reported in O (nlogd−1n + k) time using only O(n) space.}, author = {Edelsbrunner, Herbert and Overmars, Mark}, issn = {1090-2678}, journal = {Journal of Algorithms}, number = {4}, pages = {515 -- 542}, publisher = {Elsevier}, title = {{Batched dynamic solutions to decomposable searching problems}}, doi = {10.1016/0196-6774(85)90030-6}, volume = {6}, year = {1985}, } @article{4115, abstract = {A polygon in the plane is convex if it contains all line segments connecting any two of its points. Let P and Q denote two convex polygons. The computational complexity of finding the minimum and maximum distance possible between two points p in P and q in Q is studied. An algorithm is described that determines the minimum distance (together with points p and q that realize it) in O(logm + logn) time, where m and n denote the number of vertices of P and Q, respectively. This is optimal in the worst case. For computing the maximum distance, a lower bound Ω(m + n) is proved. This bound is also shown to be best possible by establishing an upper bound of O(m + n).}, author = {Edelsbrunner, Herbert}, issn = {1090-2678}, journal = {Journal of Algorithms}, number = {2}, pages = {213 -- 224}, publisher = {Academic Press}, title = {{Computing the extreme distances between two convex polygons}}, doi = {10.1016/0196-6774(85)90039-2}, volume = {6}, year = {1985}, }