|
 ABSTRACT
We develop new data structures for solving various visibility and intersection problems about a simple polygon P on n vertices. Among our results are a simple &Ogr;(n log n) algorithm for computing the illuminated subpolygon of P from a luminous side, and an &Ogr;(log n) algorithm for determining which side of P is first hit by a bullet fired from a point in a certain direction. The latter method requires preprocessing on P which takes time &Ogr;(n log n) and space &Ogr;(n). Our main new tool in attacking these problems is geometric duality on the two-sided plane.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
[1] Chazelle, B. A theorem on polygon cutting with applications , Proc. 23rd Annual FOCS Symp., 339-349, 1982.
|
| |
2
|
[2] Chazelle, B. Computing on a free tree via complexity preserving mappings, Proc. 25th Annual FOCS Symp., 358- 368, 1984.
|
| |
3
|
[3] Chazelle, B., and Guibas, L.J., Fractional Cascading: A data structuring technique with geometric applications, Efficient Algorithms workshop, Oberwalfach, W. Germany, 1984. To appear in the Proceedings of the 1985 ICALP, Nafplion, Greece.
|
| |
4
|
[4] El Gindy, H.A. An efficient algorithm for computing the weak visibility polygon from an edge in simple polygons, unpublished manuscript, McGill University, 1984.
|
| |
5
|
[5] Guibas, L., Ramshaw, L., and Stolfi, J. A kinetic framework for computational geometry, Proc. 24th Annual FOCS Symp., pp. 100-111, 1983.
|
| |
6
|
[6] Lee, D.T., and Lin, A., Computing the visibility polygon from an edge, unpublished manuscript, Northwestern Univ., 1984.
|
| |
7
|
[7] Edelsbrunner, H., Guibas, L., and Stolfi, J., Optimal point location in monotone subdivisions. DEC/SRC Technical Report #2, 1984.
|
CITED BY 21
|
|
Joseph S. B. Mitchell , David M. Mount , Subhash Suri, Query-sensitive ray shooting, Proceedings of the tenth annual symposium on Computational geometry, p.359-368, June 06-08, 1994, Stony Brook, New York, United States
|
|
|
P. Agarwal , M. Sharir, Red-Blue intersection detection algorithms, with applications to motion planning and collision detection, Proceedings of the fourth annual symposium on Computational geometry, p.70-80, June 06-08, 1988, Urbana-Champaign, Illinois, United States
|
|
|
P. D. Alevizos , J. Boissonnat , M. Yvinec, An optimal O(n log n) algorithm for contour reconstruction from rays, Proceedings of the third annual symposium on Computational geometry, p.162-170, June 08-10, 1987, Waterloo, Ontario, Canada
|
|
|
L. J. Guibas , M. Sharir , S. Sifrony, On the general motion planning problem with two degrees of freedom, Proceedings of the fourth annual symposium on Computational geometry, p.289-298, June 06-08, 1988, Urbana-Champaign, Illinois, United States
|
|
|
|
|
|
W. Lenhart , R. Pollack , J. Sack , R. Seidel , M. Sharir, Computing the link center of a simple polygon, Proceedings of the third annual symposium on Computational geometry, p.1-10, June 08-10, 1987, Waterloo, Ontario, Canada
|
|
|
|
|
|
|
|
|
|
|
|
L Guibas , J Hershberger , D Leven , M Sharir , R Tarjan, Linear time algorithms for visibility and shortest path problems inside simple polygons, Proceedings of the second annual symposium on Computational geometry, p.1-13, June 02-04, 1986, Yorktown Heights, New York, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
H. Edelsbrunner , L. J. Guibas , J. Hershberger , R. Seidel , M. Sharir, Implicitly representing arrangements of lines or segments, Proceedings of the fourth annual symposium on Computational geometry, p.56-69, June 06-08, 1988, Urbana-Champaign, Illinois, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.2