2026-07-25T11:56:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10006 2024-03-06T10:45:19Z ddc:004 open_access

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 Rectilinear link distance polygonal domain diameter radius 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^omega, n^2 + nh log h + chi^2)) time, where omega<2.373 denotes the matrix multiplication exponent and chi in Omega(n) cap O(n^2) 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(n^2 log n) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Elena Arseneva and Man-Kwun Chiu and Matias Korman and Aleksandar Markovic and Yoshio Okamoto and Aurélien Ooms and André van Renssen and Marcel Roeloffzen 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.58 urn:nbn:de:0030-drops-100060 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.58 eng https://creativecommons.org/licenses/by/3.0/legalcode