COMPACT INTERVAL TREES: A DATA STRUCTURE FOR CONVEX HULLS

In this paper, we investigate the problem of finding the common tangents of two convex polygons that intersect in two (unknown) points. First, we give a Theta(log(2) n) bound for algorithms that store the polygons in independent arrays. Second, we show how to beat the lower bound if the vertices of the convex polygons are drawn from a fixed set of n points. We introduce a data structure called a compact interval tree that supports common tangent computations, as well as the standard binary-search-based queries, in O(logn) time apiece. Third, we apply compact interval trees to solve the subpath hull query problem: given a simple path, preprocess it so that we can find the convex hull of a query subpath quickly. With O(nlog n) preprocessing, we can assemble a compact interval tree that represents the convex hull of a query subpath in O(log n) time. In order to represent arrangements of lines implicitly, Edelsbrunner et al. used a less efficient structure, called bridge trees, to solve the subpath hull query problem. Our compact interval trees improve their results by a factor of O(log n). Thus, the present paper replaces the paper on bridge trees referred to by Edelsbrunner et al.