Rectilinear link diameter and radius in a rectilinear polygonal domain

Man Kwun Chiu, Elena Arseneva, Aleksandar Markovic, Aurélien Ooms, Yoshio Okamoto, A.M. van Renssen, Marcel Roeloffzen

Onderzoeksoutput: Bijdrage aan congresAbstract

10 Downloads (Pure)

Samenvatting

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 + nh log h + χ^2)) time, where ω < 2.373 denotes the matrix multiplication exponent and χ ∈ Ω(n) ∩ O(n^2) is the number of edges of the graph of oriented distances. We also provide a faster algorithm for computing the diameter that runs in O(n^2 log n) time.
Originele taal-2Engels
Pagina's2:1-2:6
Aantal pagina's6
StatusGepubliceerd - 2018
Evenement34th European Workshop on Computational Geometry (EuroCG2018) - Berlin, Duitsland
Duur: 21 mrt 201823 mrt 2018
https://conference.imp.fu-berlin.de/eurocg18/home

Congres

Congres34th European Workshop on Computational Geometry (EuroCG2018)
Verkorte titelEuroCG2018
LandDuitsland
StadBerlin
Periode21/03/1823/03/18
Internet adres

Citeer dit

Chiu, M. K., Arseneva, E., Markovic, A., Ooms, A., Okamoto, Y., van Renssen, A. M., & Roeloffzen, M. (2018). Rectilinear link diameter and radius in a rectilinear polygonal domain. 2:1-2:6. Abstract van 34th European Workshop on Computational Geometry (EuroCG2018), Berlin, Duitsland.