✦ LIBER ✦

Ray Shooting Amidst Convex Polygons in 2D

✍ Scribed by Pankaj K. Agarwal; Micha Sharir

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 220 KB
Volume: 21
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1996.0056

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the problem of ray shooting in a two-dimensional scene consisting of m convex polygons with a total of n edges. We present a data structure that Ž . requires O mn log m space and preprocessing time and that answers a ray Ž 2 2 . shooting query in O log m log n time. If the polygons are pairwise disjoint, the ŽŽ 2 . . Ž Ž 2 space and preprocessing time can be improved to O m q n log m and O m q . . nlog n log m , respectively. Our algorithm also works for a collection of disjoint Ž . simple polygons. We also show that if we allow only O n space, a ray shooting query among a collection of disjoint simple polygons can be answered in time 1q 2 ' Žu v . O mr n log n time, for any ) 0.

📜 SIMILAR VOLUMES

Linear Data Structures for Fast Ray-Shoo

Linear Data Structures for Fast Ray-Shooting amidst Convex Polyhedra

✍ Haim Kaplan; Natan Rubin; Micha Sharir 📂 Article 📅 2008 🏛 Springer 🌐 English ⚖ 608 KB

Ray shooting in polygons using geodesic

Ray shooting in polygons using geodesic triangulations

✍ B. Chazelle; H. Edelsbrunner; M. Grigni; L. Guibas; J. Hershberger; M. Sharir; J 📂 Article 📅 1994 🏛 Springer 🌐 English ⚖ 914 KB

Hierarchical Decompositions and Circular

Hierarchical Decompositions and Circular Ray Shooting in Simple Polygons

✍ Siu-Wing Cheng; Otfried Cheong; Hazel Everett; René van Oostrum 📂 Article 📅 2004 🏛 Springer 🌐 English ⚖ 204 KB

Reconstructing Convex Polygons in the Pl

Reconstructing Convex Polygons in the Plane from One Directed X-Ray

✍ D. Lam; D. C. Solmon 📂 Article 📅 2001 🏛 Springer 🌐 English ⚖ 589 KB

A Distributed Formation of Smallest Faul

A Distributed Formation of Smallest Faulty Orthogonal Convex Polygons in 2-D Meshes

✍ Jie Wu 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 229 KB

The rectangular faulty block model is the most commonly used fault model for designing fault-tolerant and deadlock-free routing algorithms in meshconnected multicomputers. The convexity of a rectangle facilitates simple and efficient ways to route messages around fault regions using relatively few v

Hierarchical representation of 2-D shape

Hierarchical representation of 2-D shapes using convex polygons: a contour-based approach

✍ O. El Badawy; M.S. Kamel 📂 Article 📅 2005 🏛 Elsevier Science 🌐 English ⚖ 688 KB

A concavity tree is a data structure for hierarchically representing the shape of two-dimensional silhouettes using convex polygons. In this paper, we present a new algorithm for concavity tree extraction. The algorithm is fast, works directly on the pixel grid of the shape, and uses exact convex hu