Technical Report No. 56, August 1994 - Abstract

Vladimir Estivill-Castro, Sven Schuierer:
Optimal Algorithms for Stabbing Polygons by Monotone Chains

In this paper we present optimal algorithms to compute monotone stabbers for convex polygons. More precisely, given a set of m convex polygons with n vertices in total we want to stab the polygons with an x-monotone polygonal chain such that each polygon is entered at its leftmost point and departed at its rightmost point. Since such a stabber does not exist in general, we study two related problems. In the first problem we want to compute a monotone stabber that stabs as many convex polygons as possible. The second problem is to compute the minimal number of x-monotone stabbers that are necessary to stab all given convex polygons.

We present optimal O(m*log m + n) algorithms for both problems.