dc.contributor.author
Knauer, Christian
dc.contributor.author
Rote, Günter
dc.date.accessioned
2018-06-08T07:47:28Z
dc.date.available
2009-06-16T09:01:23.335Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/18705
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-22392
dc.description.abstract
We 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.
de
dc.relation.ispartofseries
urn:nbn:de:kobv:188-fudocsseries000000000021-2
dc.rights.uri
http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen
dc.subject
Computational geometry
dc.subject
Simple polygons
dc.subject
Shortest paths
dc.subject.ddc
000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung; Informatik
dc.title
Shortest inspection-path queries in simple polygons
refubium.affiliation
Mathematik und Informatik
de
refubium.affiliation.other
Institut für Informatik
refubium.mycore.fudocsId
FUDOCS_document_000000002329
refubium.resourceType.isindependentpub
no
refubium.series.name
Freie Universität Berlin, Fachbereich Mathematik und Informatik
refubium.series.reportNumber
05-5
refubium.mycore.derivateId
FUDOCS_derivate_000000000456
dcterms.accessRights.openaire
open access
