Circle shooting in a simple polygon


Journal Article

Consider the following problem: Given a simple n-gon 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, Inc.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Sharir, M

Published Date

  • January 1, 1993

Published In

Volume / Issue

  • 14 / 1

Start / End Page

  • 69 - 87

International Standard Serial Number (ISSN)

  • 0196-6774

Digital Object Identifier (DOI)

  • 10.1006/jagm.1993.1004

Citation Source

  • Scopus