Anzeige
Erschienen in:
2020 | OriginalPaper | Buchkapitel
Simplified Emanation Graphs: A Sparse Plane Spanner with Steiner Points
verfasst von : Bardia Hamedmohseni, Zahed Rahmati, Debajyoti Mondal
Erschienen in: SOFSEM 2020: Theory and Practice of Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Emanation graphs of grade k, introduced by Hamedmohseni, Rahmati, and Mondal, are plane spanners made by shooting \(2^{k+1}\) rays from each given point, where the shorter rays stop the longer ones upon collision. The collision points are the Steiner points of the spanner.
We introduce a method of simplification for emanation graphs of grade \(k=2\), which makes it a competent spanner for many possible use cases such as network visualization and geometric routing. In particular, the simplification reduces the number of Steiner points by half and also significantly decreases the total number of edges, without increasing the spanning ratio. Exact methods of simplification is provided along with comparisons of simplified emanation graphs against Shewchuk’s constrained Delaunay triangulations on both synthetic and real-life datasets. Our experimental results reveal that the simplified emanation graphs outperform constrained Delaunay triangulations in common quality measures.