Visibility Algorithms in the PlaneCambridge University Press, 29.03.2007 A human observer can effortlessly identify visible portions of geometric objects present in the environment. However, computations of visible portions of objects from a viewpoint involving thousands of objects is a time consuming task even for high speed computers. To solve such visibility problems, efficient algorithms have been designed. This book presents some of these visibility algorithms in two dimensions. Specifically, basic algorithms for point visibility, weak visibility, shortest paths, visibility graphs, link paths and visibility queries are all discussed. Several geometric properties are also established through lemmas and theorems. With over 300 figures and hundreds of exercises, this book is ideal for graduate students and researchers in the field of computational geometry. It will also be useful as a reference for researchers working in algorithms, robotics, computer graphics and geometric graph theory, and some algorithms from the book can be used in a first course in computational geometry. |
Inhalt
Point Visibility | 13 |
Weak Visibility and Shortest Paths | 46 |
LRVisibility and Shortest Paths | 105 |
Visibility Graphs | 136 |
Visibility Graph Theory | 171 |
Visibility and Link Paths | 218 |
Visibility and Path Queries | 255 |
| 295 | |
| 311 | |
Andere Ausgaben - Alle anzeigen
Häufige Begriffe und Wortgruppen
algorithm for computing algorithm of Ghosh apex assume bd(P belongs blocking vertex bounding chord C-polygon chordal graph Computational Geometry computed in O(n Consider constructed edge convex hull convex polygon counterclockwise order denote diagonals different disjoint dual graph endpoints Euclidean shortest path Figure first following lemma following theorem geodesic triangle goto Step graph G greedy path Guibas Hamiltonian cycle hourglasses intersection point interval graph invisible pairs lies inside line segment located LR-visibility polygon maximum clique minimum link path MLP(s,t Necessary condition node number of vertices O(logn permutation graph preprocessing problem procedure query algorithm query point rectilinear polygon reflex vertex region respectively right turn Section shortest path tree simple polygon spiral polygon SPT(s SPT(vi star-shaped polygon sub-graph sub-polygon tangent tower polygon traversing upper chain vertex vk vi+1 visibility cell visibility chord visibility graph visible from q visible segments vivi+1 vivj vj+1 vjvj+1 vkvk+1 weak visibility polygon
Beliebte Passagen
Seite 299 - Improved approximation algorithms for the capacitated facility location problem. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages S875-S876, 1999.
Seite 310 - Finding the Minimum Visible Vertex Distance Between Two Nonintersecting Polygons,
Seite 295 - Visibility Graphs of Staircase Polygons and the Weak Bruhat Order I : From Visibility Graphs to Maximal Chains, Discrete and Computational Geometry, Accepted (pending revisions). 4. J. Abello, K. Kumar, Visibility Graphs and Oriented Matroids (Long Version), Manuscript.
Seite 310 - M. Yamashita, H. Umemoto, I. Suzuki, and T. Kameda. Searching for mobile intruders in a polygonal region by a group of mobile searchers. Algorithmica, 31(2):208—236, 2001.
Seite 295 - A. Aggarwal, H. Booth, J. O'Rourke, S. Suri, and CK Yap. Finding minimal convex nested polygons.
Verweise auf dieses Buch
WALCOM: Algorithms and Computation: Third International Workshop, WALCOM ... Sandip Das,Ryuhei Uehara Eingeschränkte Leseprobe - 2009 |