Contents

-

Optimal Algorithms for Stabbing Polygons by Monotone Chains and Paths

Vladimir Estivill-Castro1, Sven Schuierer2
1Laboratorio Nacional de Informatica Avanzada Rébsamen 80, Xalapa Veracruz 91000, México
2Institut fiir Informatik, Universitat Freiburg Am Flughafen 17, D-79110 Freiburg, Germany

Abstract

Two algorithms to compute monotone stabbers for convex polygons are presented. More precisely, given a set of m convex polygons with n vertices in total, we want to stab the polygons with an $z$-monotone polygonal chain such that each polygon is entered at its leftmost point and exited at its rightmost point. Since such a stabber does not exist in general, we study two related problems. The first problem requests 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(mlogm+n) algorithms for both problems.