arXiv Open Access 2017

The Geodesic $2$-center Problem in a Simple Polygon

Eunjin Oh Jean-Lou De Carufel Hee-Kap Ahn

Lihat Sumber

Abstrak

The geodesic $k$-center problem in a simple polygon with $n$ vertices consists in the following. Find a set $S$ of $k$ points in the polygon that minimizes the maximum geodesic distance from any point of the polygon to its closest point in $S$. In this paper, we focus on the case where $k=2$ and present an exact algorithm that returns a geodesic $2$-center in $O(n^2\log^2 n)$ time.

Topik & Kata Kunci

cs.CG

Penulis (3)

Eunjin Oh

Jean-Lou De Carufel

Hee-Kap Ahn

Format Sitasi

APA MLA BibTeX

Oh, E., Carufel, J.D., Ahn, H. (2017). The Geodesic $2$-center Problem in a Simple Polygon. https://arxiv.org/abs/1710.09035

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2017
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓