Math @ Duke

Publications [#235571] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Sharir, M, Circle Shooting in a Simple Polygon,
Journal of Algorithms, vol. 14 no. 1
(1993),
pp. 6987, ISSN 01966774 [doi]
(last updated on 2018/03/18)
Abstract: Consider the following problem: Given a simple ngon P, preprocess it so that for a query circle π and a point s on π, one can quickly compute Φ(P, π, s), the first intersection point between P and π as we follow π from s in clockwise direction. We show that P can be preprocessed, in time O(n log3n), into a data structure of size O(n log3n), so that, for a query circle π, Φ(P, π, s) can be computed in O(log4n) time. We apply the circle shooting algorithm to report all K intersections between a set of m circular arcs and another set of n circular arcs in time O((m√n + n√m )log2.5(m + n) + (K + m + n)log4(m + n)). © 1993 Academic Press. All rights reserved.


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

