ZIB

Treffer pro Seite

Treffer 1 - 1 | 1 Treffer

Sortierung

Digitale Medien

Visibility of disjoint polygons (1986)

Asano, Takao ; Asano, Tetsuo ; Guibas, Leonidas ; [weitere]

Springer

Algorithmica 1 (1986), S. 49-63

zur Merkliste hinzufügen auf der Merkliste

Details

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

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

Artikel (Nationallizenzen)

Volltext

Treffer 1 - 1 | 1 Treffer