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.
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 documentWorking paper
Terms of use/Rights Nutzungsbedingungen
Created at2009-06-16 : 09:01:23
Last changed2015-03-25 : 12:51:41
Static URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000002329