Computing Common Tangents Without a Separating Line ?

David Kirkpatrick Jack Snoeyink

Department of Computer Science
University of British Columbia

Abstract

Given two disjoint convex polygons in standard representations, one can compute outer common tangents in logarithmic time without first obtaining a separating line. If the polygons are not disjoint, there is an additional factor of the logarithm of the intersection or union size, whichever is smaller.

1 Introduction

In this paper, we revisit an old problem: computing a tangent line common to two disjoint polygons, P and Q, that are represented by ordered lists of n vertices stored in arrays or balanced binary trees.

Because a tangent to a polygon P through a given point q can be found in ?(log n) time by binary search, there is an easy O(log2 n) time algorithm for finding a tangent common to P and Q that uses nested binary search. Overmars and van Leeuwen [7], as part of a data structure for dynamic convex hulls, gave a logarithmic-time algorithm for the special case in which P and Q have a known vertical separating line. Because one can compute a separating line for disjoint polygons in logarithmic time|by finding the shortest segment joining them [3] or using hierarchical representations [2, 6]|the Overmars/van Leeuwen algorithm gives a complete solution.

For three reasons, however, it is still interesting to ask whether a common tangent can be computed without the knowledge of the separator. First, there are common tangent problems (and intersection problems, which are their duals) that cannot be solved by one level of binary search. Guibas et al. [5] have shown that to compute an outer common tangent to intersecting polygons P and Q requires ?(log2 n) time, even if points in P ?Q and Q? P are given. Second, Overmars and van Leeuwen's data structure has been adapted for other purposes that do not have a vertical bias|including implicit storage of arrangements [4, 5], ray shooting [1], etc.|so that an affirmative answer simplifies and speeds up these applications by a constant factor. Third, it is natural to look for common tangents in situations where no separating line exists.

In the next section, we show that tangents for disjoint convex polygons can be computed in logarithmic time by using a tentative prune-and-search technique [6]. C code is given in an appendix. The approach is much like Overmars and van Leeuwen's [7]|starting with lists of vertices for P and for Q that are known to contain the tangent vertices, attempt to discard half of some list by doing a constant-time local test. Without a separating line, however, some tests do not give sufficient information. One can proceed by making tentative discards that are later

?Both authors supported in part by NSERC Research Grants. The second was also supported by a fellowship from the B.C. Advanced Systems Institute.