Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235510] of Pankaj K. Agarwal

Papers Published

  1. 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 (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5193 LNCS (2008), pp. 52-63, ISSN 0302-9743 [doi]
    (last updated on 2018/10/22)

    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 k-gon. 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 pairwise-disjoint, (ii) B is a line segment and the obstacles in O may intersect (iii) B is a convex k-gon and the obstacles in O are disjoint, and use these improved bounds to analyze the running time of our stabbing-set algorithm. © 2008 Springer-Verlag Berlin Heidelberg.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320