liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Computing the $ L_1 $ Geodesic Diameter and Center of a Polygonal Domain
Kyonggi University, Suwon, South Korea.
Tohoku University, Sendai, Japan.
Stony Brook University, New York, USA.
The University of Electro-Communications, Tokyo, Japan.
Show others and affiliations
2016 (English)In: Leibniz International Proceedings in Informatics, ISSN 1868-8969, E-ISSN 1868-8969, Vol. 47, 14:1-14:14 p.Article in journal (Refereed) PublishedText
Abstract [en]

For a polygonal domain with h holes and a total of n vertices, we present algorithms that compute the L1 geodesic diameter in O(n2+h4) time and the L1 geodesic center in O((n4+n2h4) (n)) time, where (·) denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in O(n7.73) or O(n7(h+log n)) time, and compute the geodesic center in O(n12+) time. Therefore, our algorithms are much faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on L1 shortest paths in polygonal domains.

Place, publisher, year, edition, pages
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik , 2016. Vol. 47, 14:1-14:14 p.
Keyword [en]
geodesic diameter, geodesic center, shortest paths, polygonal domains, L1 metric
National Category
Computer Science Medical Image Processing
URN: urn:nbn:se:liu:diva-128031DOI: 10.4230/LIPIcs.STACS.2016.14OAI: diva2:928732
Available from: 2016-05-16 Created: 2016-05-16 Last updated: 2016-08-30

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Polishchuk, Valentin
By organisation
Communications and Transport SystemsFaculty of Science & Engineering
In the same journal
Leibniz International Proceedings in Informatics
Computer ScienceMedical Image Processing

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 156 hits
ReferencesLink to record
Permanent link

Direct link