Please use this identifier to cite or link to this item:
For citation please use:
Main Title: A fast shortest path algorithm on terrain-like graphs
Author(s): Froese, Vincent
Renken, Malte
Type: Article
Abstract: Terrain visibility graphs are a well-known graph class in computational geometry. They are closely related to polygon visibility graphs, but a precise graph-theoretical characterization is still unknown. Over the last decade, terrain visibility graphs attracted considerable attention in the context of time series analysis (there called time series visibility graphs) with various practical applications in areas such as physics, geography, and medical sciences. Computing shortest paths in visibility graphs is a common task, for example, in line-of-sight communication. For time series analysis, graph characteristics involving shortest paths lengths (such as centrality measures) have proven useful. In this paper, we devise a fast output-sensitive shortest path algorithm on a superclass of terrain visibility graphs called terrain-like graphs (including all induced subgraphs of terrain visibility graphs). Our algorithm runs in  O ( d ∗ log Δ ) time, where d ∗ is the length (that is, the number of edges) of the shortest path and Δ is the maximum vertex degree. Alternatively, with an O(n^2) -time preprocessing our algorithm runs in O ( d ∗ ) time.
Subject(s): output-sensitive algorithm
polygon visibility graphs
time series visibility graphs
vertex ordering
terrain-like graphs
Issue Date: 4-Aug-2020
Date Available: 12-Mar-2021
Language Code: en
DDC Class: 510 Mathematik
Sponsor/Funder: TU Berlin, Open-Access-Mittel – 2020
Journal Title: Discrete and Computational Geometry
Publisher: SpringerNature
Publisher DOI: 10.1007/s00454-020-00226-8
EISSN: 1432-0444
ISSN: 0179-5376
TU Affiliation(s): Fak. 4 Elektrotechnik und Informatik » Inst. Softwaretechnik und Theoretische Informatik » FG Algorithmik und Komplexitätstheorie
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 427.11 kB
DownloadShow Preview

Item Export Bar

This item is licensed under a Creative Commons License Creative Commons