### 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.

report56.ps.gz