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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Computing the L-1 Geodesic Diameter and Center of a Polygonal Domain
Kyonggi University, South Korea.
Tohoku University, Japan.
SUNY Stony Brook, NY USA.
University of Electrocommun, Japan.
Show others and affiliations
2017 (English)In: Discrete & Computational Geometry, ISSN 0179-5376, E-ISSN 1432-0444, Vol. 57, no 3, p. 674-701Article in journal (Refereed) Published
Abstract [en]

For a polygonal domain with h holes and a total of n vertices, we present algorithms that compute the geodesic diameter in time and the geodesic center in time, respectively, 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 or time, and compute the geodesic center in time. Therefore, our algorithms are significantly faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on shortest paths in polygonal domains.

Place, publisher, year, edition, pages
SPRINGER , 2017. Vol. 57, no 3, p. 674-701
Keywords [en]
Geodesic diameter; Geodesic center; Shortest paths; Polygonal domains; L-1 metric
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-136571DOI: 10.1007/s00454-016-9841-zISI: 000395193000009OAI: oai:DiVA.org:liu-136571DiVA, id: diva2:1090307
Note

Funding Agencies|Basic Science Research Program through the National Research Foundation of Korea (NRF) - Ministry of Science, ICT & Future Planning [2013R1A1A1A05006927]; Ministry of Education [2015R1D1A1A01057220]; JSPS/MEXT [12H00855, 15H02665, JP24106005, JP24700008, JP24220003, JP15K00009]; MEXT KAKENHI [24106008]; US-Israel Binational Science Foundation [2010074]; National Science Foundation [CCF-1018388, CCF-1526406, CCF-1317143]; JST, CREST, Foundation of Innovative Algorithms for Big Data; Swedens innovation agency VINNOVA [2014-03476]; Swedish Transport Administration Trafikverket

Available from: 2017-04-24 Created: 2017-04-24 Last updated: 2017-04-24

Open Access in DiVA

No full text in DiVA

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
Discrete & Computational Geometry
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 95 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf