Rectilinear link diameter and radius in a rectilinear polygonal domain

DOI DOI DOI HANDLE HANDLE ほか2件をすべて表示 一部だけ表示 参考文献23件

この論文をさがす

説明

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 \emph{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 $\min \{\,O(n^��), O(n^2 + nh \log h + ��^2)\,\}$ time, where $��<2.373$ denotes the matrix multiplication exponent and $��\in ��(n)\cap 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.

収録刊行物

参考文献 (23)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

問題の指摘

ページトップへ