Planar point location using persistent search trees.

*(English)*Zbl 0732.68102
Combinatorial mathematics, Proc. 3rd Int. Conf., New York/ NY (USA) 1985, Ann. N. Y. Acad. Sci. 555, 352-362 (1989).

[For the entire collection see Zbl 0699.00014.]

[The full version of this paper appeared in Commun. ACM 29, No.7, 669-679 (1986)].

Let us consider a classical geometric retrieval problem. Suppose the Euclidean plane is subdivided into polygons by n line segments that intersect only at their endpoints. Given such a polygonal subdivision and a sequence of query points in the plane, the planar point location problem is the problem of determining for each query point, the polygon containing it. (For simplicity we shall assume that no query point lies on a line segment of the subdivision.) We require that the answers to the queries be produced on-line; that is, each point must be located before the next point is known.

A solution to the point location problem consists of an algorithm that preprocesses the polygonal subdivision, building a data structure that facilitates location of individual query points. We measure the efficiency of such a solution by three parameters: the preprocessing time, the space required to store the data structure, and the time per query. Of these, the preprocessing time is generally the least important.

Our main result, presented in the third section, is a persistent form of binary search tree with an O(log m) worst case access/insert/delete time and an amortized space requirement of O(1) per update. Our structure has neither of the drawbacks of R. Cole’s [J. Algorithms 7, 202-220 (1986; Zbl 0605.68053)]. It provides a simple O(n)-space, O(log n)-query- time point location algorithm. It can also replace Chazelle’s “hive graph” B. Chazelle [Filtering search: A new approach to query answering. Proc. of the 24th Annual IEEE Symp. on Foundations of Computer Science, 122-132 (1983)], a rather complicated data structure with a variety of uses in geometric searching.

[The full version of this paper appeared in Commun. ACM 29, No.7, 669-679 (1986)].

Let us consider a classical geometric retrieval problem. Suppose the Euclidean plane is subdivided into polygons by n line segments that intersect only at their endpoints. Given such a polygonal subdivision and a sequence of query points in the plane, the planar point location problem is the problem of determining for each query point, the polygon containing it. (For simplicity we shall assume that no query point lies on a line segment of the subdivision.) We require that the answers to the queries be produced on-line; that is, each point must be located before the next point is known.

A solution to the point location problem consists of an algorithm that preprocesses the polygonal subdivision, building a data structure that facilitates location of individual query points. We measure the efficiency of such a solution by three parameters: the preprocessing time, the space required to store the data structure, and the time per query. Of these, the preprocessing time is generally the least important.

Our main result, presented in the third section, is a persistent form of binary search tree with an O(log m) worst case access/insert/delete time and an amortized space requirement of O(1) per update. Our structure has neither of the drawbacks of R. Cole’s [J. Algorithms 7, 202-220 (1986; Zbl 0605.68053)]. It provides a simple O(n)-space, O(log n)-query- time point location algorithm. It can also replace Chazelle’s “hive graph” B. Chazelle [Filtering search: A new approach to query answering. Proc. of the 24th Annual IEEE Symp. on Foundations of Computer Science, 122-132 (1983)], a rather complicated data structure with a variety of uses in geometric searching.