Navigation/Menü: Links auf weitere Seiten dieser Website
Objekt-Metadaten
| Shortest inspection-path queries in simple polygons Knauer, Christian |
| Haupttitel | Shortest inspection-path queries in simple polygons |
| Autor | Knauer, Christian; Rote, Günter |
| Seitenzahl | 6 S. |
| Schriftenreihe | Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; [20]05,05 |
| Fachbereich/Einrichtung | FB Mathematik und Informatik |
| Arbeitsbereich/Institut | Institut für Informatik |
| Erscheinungsjahr | 2005 |
| Dokumente | PDF-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
|
| Freie Schlagwörter | Computational geometry, Simple polygons, Shortest paths, Visibility |
| DDC | 004 Datenverarbeitung; Informatik |
| Dokumententyp/-Sammlungen | Report |
| Medientyp/Format | Text |
| 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. |
| Sprache | Englisch |
| Rechte | Nutzungsbedingungen |
| Zugriffstatistik | |
| Statische URL | http://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000002329 |
| Erstellt am | 16.06.2009 - 11:01:23 |
| Letzte Änderung | 04.04.2013 - 09:33:27 |
