Standard
Rectilinear link diameter and radius in a rectilinear polygonal domain. / Arseneva, Elena; Chiu, Man Kwun; Korman, Matias; Markovic, Aleksandar; Okamoto, Yoshio; Ooms, Aurélien; Van Renssen, André; Roeloffzen, Marcel.
29th International Symposium on Algorithms and Computation, ISAAC 2018. ed. / Chung-Shou Liao; Wen-Lian Hsu; Der-Tsai Lee. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. p. 58:1-58:13 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 123).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Harvard
Arseneva, E, Chiu, MK, Korman, M, Markovic, A, Okamoto, Y, Ooms, A, Van Renssen, A & Roeloffzen, M 2018,
Rectilinear link diameter and radius in a rectilinear polygonal domain. in C-S Liao, W-L Hsu & D-T Lee (eds),
29th International Symposium on Algorithms and Computation, ISAAC 2018. Leibniz International Proceedings in Informatics, LIPIcs, vol. 123, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 58:1-58:13, 29th International Symposium on Algorithms and Computation, ISAAC 2018, Jiaoxi, Yilan, Taiwan, Province of China,
16/12/18.
https://doi.org/10.4230/LIPIcs.ISAAC.2018.58
APA
Arseneva, E., Chiu, M. K., Korman, M., Markovic, A., Okamoto, Y., Ooms, A., Van Renssen, A., & Roeloffzen, M. (2018).
Rectilinear link diameter and radius in a rectilinear polygonal domain. In C-S. Liao, W-L. Hsu, & D-T. Lee (Eds.),
29th International Symposium on Algorithms and Computation, ISAAC 2018 (pp. 58:1-58:13). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 123). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
https://doi.org/10.4230/LIPIcs.ISAAC.2018.58
Vancouver
Arseneva E, Chiu MK, Korman M, Markovic A, Okamoto Y, Ooms A et al.
Rectilinear link diameter and radius in a rectilinear polygonal domain. In Liao C-S, Hsu W-L, Lee D-T, editors, 29th International Symposium on Algorithms and Computation, ISAAC 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2018. p. 58:1-58:13. (Leibniz International Proceedings in Informatics, LIPIcs).
https://doi.org/10.4230/LIPIcs.ISAAC.2018.58
Author
Arseneva, Elena ; Chiu, Man Kwun ; Korman, Matias ; Markovic, Aleksandar ; Okamoto, Yoshio ; Ooms, Aurélien ; Van Renssen, André ; Roeloffzen, Marcel. /
Rectilinear link diameter and radius in a rectilinear polygonal domain. 29th International Symposium on Algorithms and Computation, ISAAC 2018. editor / Chung-Shou Liao ; Wen-Lian Hsu ; Der-Tsai Lee. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. pp. 58:1-58:13 (Leibniz International Proceedings in Informatics, LIPIcs).
BibTeX
@inproceedings{0430e066885b4f4a8e5673014f26adf8,
title = "Rectilinear link diameter and radius in a rectilinear polygonal domain",
abstract = "We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of n vertices and h holes. We introduce a graph of oriented distances to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in O(min(nω, n2 + nhlog h + χ2)) time, where ω < 2.373 denotes the matrix multiplication exponent and χ ∈ Ω(n) ∩ O(n2) is the number of edges of the graph of oriented distances. We also provide an alternative algorithm for computing the diameter that runs in O(n2 log n) time.",
keywords = "Diameter, Polygonal domain, Radius, Rectilinear link distance",
author = "Elena Arseneva and Chiu, {Man Kwun} and Matias Korman and Aleksandar Markovic and Yoshio Okamoto and Aur{\'e}lien Ooms and {Van Renssen}, Andr{\'e} and Marcel Roeloffzen",
year = "2018",
month = dec,
day = "1",
doi = "10.4230/LIPIcs.ISAAC.2018.58",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "58:1--58:13",
editor = "Chung-Shou Liao and Wen-Lian Hsu and Der-Tsai Lee",
booktitle = "29th International Symposium on Algorithms and Computation, ISAAC 2018",
address = "Germany",
note = "29th International Symposium on Algorithms and Computation, ISAAC 2018 ; Conference date: 16-12-2018 Through 19-12-2018",
}
RIS
TY - GEN
T1 - Rectilinear link diameter and radius in a rectilinear polygonal domain
AU - Arseneva, Elena
AU - Chiu, Man Kwun
AU - Korman, Matias
AU - Markovic, Aleksandar
AU - Okamoto, Yoshio
AU - Ooms, Aurélien
AU - Van Renssen, André
AU - Roeloffzen, Marcel
PY - 2018/12/1
Y1 - 2018/12/1
N2 - We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of n vertices and h holes. We introduce a graph of oriented distances to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in O(min(nω, n2 + nhlog h + χ2)) time, where ω < 2.373 denotes the matrix multiplication exponent and χ ∈ Ω(n) ∩ O(n2) is the number of edges of the graph of oriented distances. We also provide an alternative algorithm for computing the diameter that runs in O(n2 log n) time.
AB - We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of n vertices and h holes. We introduce a graph of oriented distances to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in O(min(nω, n2 + nhlog h + χ2)) time, where ω < 2.373 denotes the matrix multiplication exponent and χ ∈ Ω(n) ∩ O(n2) is the number of edges of the graph of oriented distances. We also provide an alternative algorithm for computing the diameter that runs in O(n2 log n) time.
KW - Diameter
KW - Polygonal domain
KW - Radius
KW - Rectilinear link distance
UR - http://www.scopus.com/inward/record.url?scp=85063694845&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ISAAC.2018.58
DO - 10.4230/LIPIcs.ISAAC.2018.58
M3 - Conference contribution
AN - SCOPUS:85063694845
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 58:1-58:13
BT - 29th International Symposium on Algorithms and Computation, ISAAC 2018
A2 - Liao, Chung-Shou
A2 - Hsu, Wen-Lian
A2 - Lee, Der-Tsai
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 29th International Symposium on Algorithms and Computation, ISAAC 2018
Y2 - 16 December 2018 through 19 December 2018
ER -
