Dokumentenserver der Freien Universität Berlin

Objekt-Metadaten

Shortest inspection-path queries in simple polygons
Knauer, Christian ;  Rote, Günter ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

HaupttitelShortest inspection-path queries in simple polygons
AutorKnauer, Christian
AutorRote, Günter
Institution/KörperschaftUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
Seitenzahl6 S.
Schriftenreihe Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; [20]05,05
Freie SchlagwörterComputational geometry, Simple polygons, Shortest paths, Visibility
DDC004 Datenverarbeitung; Informatik
ZusammenfassungWe want to preprocess a simple n-vertex polygon P to
quickly determine the shortest path from a fixed source point s 2 P
to some point visible from a query point q 2 P. We call such queries
inspection-path queries.We give an algorithm that computes a data structure
which answers the queries in logarithmic time. The data structure
has O(n) size and can be computed in O(n log n) time.
Dokumente
PDF-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
 
Fachbereich/EinrichtungFB Mathematik und Informatik
Arbeitsbereich/InstitutInstitut für Informatik
Erscheinungsjahr2005
Dokumententyp/-SammlungenKarten
SpracheEnglisch
Rechte Nutzungsbedingungen
Erstellt am16.06.2009 - 09:01:23
Letzte Änderung23.01.2014 - 16:21:30
 
Statische URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000002329
Zugriffsstatistik