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 congresAbstractAcademic

32 Downloads (Pure)


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
Aantal pagina's6
StatusGepubliceerd - 2018
Evenement34th European Workshop on Computational Geometry (EuroCG2018) - Berlin, Duitsland
Duur: 21 mrt 201823 mrt 2018


Congres34th European Workshop on Computational Geometry (EuroCG2018)
Verkorte titelEuroCG2018
Internet adres


Duik in de onderzoeksthema's van 'Rectilinear link diameter and radius in a rectilinear polygonal domain'. Samen vormen ze een unieke vingerafdruk.

Citeer dit