License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2016.14
URN: urn:nbn:de:0030-drops-67858
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6785/
Go to the corresponding LIPIcs Volume Portal

Bae, Sang Won

L_1 Geodesic Farthest Neighbors in a Simple Polygon and Related Problems

pdf-format:
LIPIcs-ISAAC-2016-14.pdf (0.6 MB)

Abstract

In this paper, we investigate the L_1 geodesic farthest neighbors in a simple polygon P, and address several fundamental problems related to farthest neighbors. Given a subset S subseteq P, an L_1 geodesic farthest neighbor of p in P from S is one that maximizes the length of L_1 shortest path from p in P. Our list of problems include: computing the diameter, radius, center, farthest-neighbor Voronoi diagram, and two-center of S under the L_1 geodesic distance. We show that all these problems can be solved in linear or near-linear time based on our new observations on farthest neighbors and extreme points. Among them, the key observation shows that there are at most four extreme points of any compact subset S subseteq P with respect to the L_1 geodesic distance after removing redundancy.

BibTeX - Entry

@InProceedings{bae:LIPIcs:2016:6785,
  author =	{Sang Won Bae},
  title =	{{L_1 Geodesic Farthest Neighbors in a Simple Polygon and Related Problems}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{14:1--14:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6785},
  URN =		{urn:nbn:de:0030-drops-67858},
  doi =		{10.4230/LIPIcs.ISAAC.2016.14},
  annote =	{Keywords: simple polygon, L_1 geodesic distance, farthest neighbor, farthest-neighbor Voronoi diagram, k-center}
}

Keywords: simple polygon, L_1 geodesic distance, farthest neighbor, farthest-neighbor Voronoi diagram, k-center
Collection: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 07.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI