ISSN:
1432-0541
Schlagwort(e):
Computational geometry
;
Computer graphics
;
Robotics
;
Visibility
;
Hidden-line Elimination
;
Visibility graph
;
Shortest path
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
Abstract Consider a collection of disjoint polygons in the plane containing a total ofn edges. We show how to build, inO(n 2) time and space, a data structure from which inO(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed inO(n 2) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed inO(n 2) time, improving earlierO(n 2 logn) results.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01840436
Permalink