Math @ Duke

Publications [#235510] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Chen, DZ; Ganjugunte, SK; Misiołek, E; Sharir, M; Tang, K, Stabbing convex polygons with a segment or a polygon,
Lecture notes in computer science, vol. 5193 LNCS
(2008),
pp. 5263, ISSN 03029743 [doi]
(last updated on 2018/03/18)
Abstract: Let O = {O1, . . . , Om} be a set of m convex polygons in ℝ2 with a total of n vertices, and let B be another convex kgon. A placement of B, any congruent copy of B (without reflection), is called free if B does not intersect the interior of any polygon in at this placement. A placement z of B is called critical if B forms three "distinct" contacts with at z. Let be the number of free critical placements. A set of placements of B is called a stabbing set of if each polygon in intersects at least one placement of B in this set. We develop efficient Monte Carlo algorithms that compute a stabbing set of size h = O(h *logm), with high probability, where h * is the size of the optimal stabbing set of O. We also improve bounds on (B, O) for the following three cases, namely, (i) B is a line segment and the obstacles in are O pairwisedisjoint, (ii) B is a line segment and the obstacles in O may intersect (iii) B is a convex kgon and the obstacles in O are disjoint, and use these improved bounds to analyze the running time of our stabbingset algorithm. © 2008 SpringerVerlag Berlin Heidelberg.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

