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

Main titleShortest inspection-path queries in simple polygons
AuthorKnauer, Christian
AuthorRote, Günter
InstitutionUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
No. of Pages6 S.
Series Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; [20]05,05
KeywordsComputational geometry, Simple polygons, Shortest paths, Visibility
Classification (DDC)004 Data processing and Computer science
AbstractWe 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.
Documents
PDF-Datei
If your browser can't open the file, please download the file first and then open it
 
FU DepartmentDepartment of Mathematics and Computer Science
Other affiliation(s)Institut für Informatik
Year of publication2005
Type of documentMaps
LanguageEnglish
Terms of use/Rights Nutzungsbedingungen
Created at2009-06-16 : 09:01:23
Last changed2014-01-23 : 04:21:30
 
Static URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000002329
Statistics
 

LOADING...