Oriented Spanners

Kevin Buchin; Joachim Gudmundsson; Antonia Kalb; Aleksandr Popov; Carolin Rehs; André van Renssen; Sampson Wong

Oriented Spanners

Kevin Buchin
, Joachim Gudmundsson
, Antonia Kalb
, Aleksandr Popov
, Carolin Rehs
, André van Renssen
, Sampson Wong

Algorithms

Onderzoeksoutput: Bijdrage aan congres › Paper › Academic

13 Downloads (Pure)

Samenvatting

Given a point set P and a parameter t, a (directed) geometric t-spanner G = (P, E) is a subgraph of the complete (bi-directed) graph such that for every pair of points the shortest path in G is at most a factor t longer than the corresponding Euclidean distance.
In this paper, we introduce a new model: the oriented (geometric) spanner. This is a directed graph where every edge is one-way, i.e. (p, p') ∈ E → (p', p) ∉ E. We investigate bounds for the minimal dilation. For 2-dimensional point sets, we prove NP-hardness of computing a minimal oriented dilation graph. For 1-dimensional point sets, 1-spanners are trivial to obtain. Therefore, we restrict the graphs: We present a dynamic program to compute a 1-page planar minimal oriented dilation graph in O(n⁸) time and a greedy algorithm to compute a constant dilation spanner in O(n³) time.

Originele taal-2	Engels
Pagina's	46:1-46:9
Aantal pagina's	9
Status	Gepubliceerd - 18 apr. 2023
Evenement	39th European Workshop on Computational Geometry (EuroCG 2023) - Universitat Politècnica de Catalunya, Barcelona, Spanje Duur: 29 mrt. 2023 → 31 mrt. 2023 Congresnummer: 39 https://dccg.upc.edu/eurocg23/

Workshop

Workshop	39th European Workshop on Computational Geometry (EuroCG 2023)
Verkorte titel	EuroCG 2023
Land/Regio	Spanje
Stad	Barcelona
Periode	29/03/23 → 31/03/23
Internet adres	https://dccg.upc.edu/eurocg23/

Toegang tot document

pdfDefinitieve gepubliceerde versie, 7,84 MB

Oriented Spanners
Buchin, K., Gudmundsson, J., Kalb, A., Popov, A., Rehs, C., van Renssen, A. M. & Wong, S., 30 aug. 2023, 31st Annual European Symposium on Algorithms (ESA 2023). Li Gørtz, I., Farach-Colton, M., Puglisi, S. J. & Herman, G. (reds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, blz. 26:1-26:16 16 blz. 26. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 274).
Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

Open Access
Bestand
2 Link wordt geopend op een nieuw tabblad Citaten (Scopus)

16 Downloads (Pure)

Citeer dit

@conference{65401c7d6f744b36ae40286b96023675,

title = "Oriented Spanners",

abstract = "Given a point set P and a parameter t, a (directed) geometric t-spanner G = (P, E) is a subgraph of the complete (bi-directed) graph such that for every pair of points the shortest path in G is at most a factor t longer than the corresponding Euclidean distance. In this paper, we introduce a new model: the oriented (geometric) spanner. This is a directed graph where every edge is one-way, i.e. (p, p') ∈ E → (p', p) ∉ E. We investigate bounds for the minimal dilation. For 2-dimensional point sets, we prove NP-hardness of computing a minimal oriented dilation graph. For 1-dimensional point sets, 1-spanners are trivial to obtain. Therefore, we restrict the graphs: We present a dynamic program to compute a 1-page planar minimal oriented dilation graph in O(n8) time and a greedy algorithm to compute a constant dilation spanner in O(n3) time.",

keywords = "spanner, oriented graph, greedy triangulation",

author = "Kevin Buchin and Joachim Gudmundsson and Antonia Kalb and Aleksandr Popov and Carolin Rehs and \{van Renssen\}, Andr{\'e} and Sampson Wong",

year = "2023",

month = apr,

day = "18",

language = "English",

pages = "46:1--46:9",

note = "39th European Workshop on Computational Geometry (EuroCG 2023), EuroCG 2023 ; Conference date: 29-03-2023 Through 31-03-2023",

url = "https://dccg.upc.edu/eurocg23/",

}

TY - CONF

T1 - Oriented Spanners

AU - Buchin, Kevin

AU - Gudmundsson, Joachim

AU - Kalb, Antonia

AU - Popov, Aleksandr

AU - Rehs, Carolin

AU - van Renssen, André

AU - Wong, Sampson

N1 - Conference code: 39

PY - 2023/4/18

Y1 - 2023/4/18

N2 - Given a point set P and a parameter t, a (directed) geometric t-spanner G = (P, E) is a subgraph of the complete (bi-directed) graph such that for every pair of points the shortest path in G is at most a factor t longer than the corresponding Euclidean distance. In this paper, we introduce a new model: the oriented (geometric) spanner. This is a directed graph where every edge is one-way, i.e. (p, p') ∈ E → (p', p) ∉ E. We investigate bounds for the minimal dilation. For 2-dimensional point sets, we prove NP-hardness of computing a minimal oriented dilation graph. For 1-dimensional point sets, 1-spanners are trivial to obtain. Therefore, we restrict the graphs: We present a dynamic program to compute a 1-page planar minimal oriented dilation graph in O(n8) time and a greedy algorithm to compute a constant dilation spanner in O(n3) time.

AB - Given a point set P and a parameter t, a (directed) geometric t-spanner G = (P, E) is a subgraph of the complete (bi-directed) graph such that for every pair of points the shortest path in G is at most a factor t longer than the corresponding Euclidean distance. In this paper, we introduce a new model: the oriented (geometric) spanner. This is a directed graph where every edge is one-way, i.e. (p, p') ∈ E → (p', p) ∉ E. We investigate bounds for the minimal dilation. For 2-dimensional point sets, we prove NP-hardness of computing a minimal oriented dilation graph. For 1-dimensional point sets, 1-spanners are trivial to obtain. Therefore, we restrict the graphs: We present a dynamic program to compute a 1-page planar minimal oriented dilation graph in O(n8) time and a greedy algorithm to compute a constant dilation spanner in O(n3) time.

KW - spanner

KW - oriented graph

KW - greedy triangulation

M3 - Paper

SP - 46:1-46:9

T2 - 39th European Workshop on Computational Geometry (EuroCG 2023)

Y2 - 29 March 2023 through 31 March 2023

ER -

Oriented Spanners

Samenvatting

Workshop

Toegang tot document

Vingerafdruk

Onderzoekersoutput

Oriented Spanners

Citeer dit