SHORTEST PATH TO A SEGMENT AND QUICKEST VISIBILITY QUERIES

Persistent Link:
http://hdl.handle.net/10150/614771
Title:
SHORTEST PATH TO A SEGMENT AND QUICKEST VISIBILITY QUERIES
Author:
Arkin, Esther M.; Efrat, Alon; Knauer, Christian; Mitchell, Joseph S. B.; Polishchuk, Valentin; Rote, Guenter; Schlipf, Lena; Talvitie, Topi
Affiliation:
Univ Arizona, Comp Sci
Issue Date:
2016
Publisher:
CARLETON UNIV, DEPT MATHEMATICS & STATISTICS
Journal:
JOURNAL OF COMPUTATIONAL GEOMETRY
Rights:
© Esther M. Arkin, Alon Efrat, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Günter Rote, Lena Schlipf, Topi Talvitie; licensed under Creative Commons License CC-BY
Collection Information:
This item from the UA Faculty Publications collection is made available by the University of Arizona with support from the University of Arizona Libraries. If you have questions, please contact us at repository@u.library.arizona.edu.
Abstract:
We show how to preprocess a polygonal domain with a fixed starting point s in order to answer efficiently the following queries: Given a point q, how should one move from s in order to see q as soon as possible? This query resembles the well-known shortest-path-to-a-point query, except that the latter asks for the fastest way to reach q, instead of seeing it. Our solution methods include a data structure for a different generalization of shortest-path-to-a-point queries, which may be of independent interest: to report efficiently a shortest path from s to a query segment in the domain.
Description:
31st International Symposium on Computational Geometry (SoCG 2015)
Version:
Final published version
Additional Links:
http://drops.dagstuhl.de/opus/volltexte/2015/5147/pdf/64.pdf

Full metadata record

DC FieldValue Language
dc.contributor.authorArkin, Esther M.en
dc.contributor.authorEfrat, Alonen
dc.contributor.authorKnauer, Christianen
dc.contributor.authorMitchell, Joseph S. B.en
dc.contributor.authorPolishchuk, Valentinen
dc.contributor.authorRote, Guenteren
dc.contributor.authorSchlipf, Lenaen
dc.contributor.authorTalvitie, Topien
dc.date.accessioned2016-06-25T01:23:27Z-
dc.date.available2016-06-25T01:23:27Z-
dc.date.issued2016-
dc.identifier.urihttp://hdl.handle.net/10150/614771-
dc.description31st International Symposium on Computational Geometry (SoCG 2015)en
dc.description.abstractWe show how to preprocess a polygonal domain with a fixed starting point s in order to answer efficiently the following queries: Given a point q, how should one move from s in order to see q as soon as possible? This query resembles the well-known shortest-path-to-a-point query, except that the latter asks for the fastest way to reach q, instead of seeing it. Our solution methods include a data structure for a different generalization of shortest-path-to-a-point queries, which may be of independent interest: to report efficiently a shortest path from s to a query segment in the domain.en
dc.language.isoenen
dc.publisherCARLETON UNIV, DEPT MATHEMATICS & STATISTICSen
dc.relation.urlhttp://drops.dagstuhl.de/opus/volltexte/2015/5147/pdf/64.pdfen
dc.rights© Esther M. Arkin, Alon Efrat, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Günter Rote, Lena Schlipf, Topi Talvitie; licensed under Creative Commons License CC-BYen
dc.titleSHORTEST PATH TO A SEGMENT AND QUICKEST VISIBILITY QUERIESen
dc.typeArticleen
dc.contributor.departmentUniv Arizona, Comp Scien
dc.identifier.journalJOURNAL OF COMPUTATIONAL GEOMETRYen
dc.description.collectioninformationThis item from the UA Faculty Publications collection is made available by the University of Arizona with support from the University of Arizona Libraries. If you have questions, please contact us at repository@u.library.arizona.edu.en
dc.eprint.versionFinal published versionen
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.