Computing the link center of a simple polygon
type: Item
instance of: scholarly article
title: Computing the link center of a simple polygon
zbMATH Open document ID: 0646.68056
DOI: 10.1007/BF02187913
author: Jörg-Rüdiger Sack
author: Raimund Seidel
author: Micha Sharir
author: Godfried Toussaint
author: William Lenhart
author: Richard Pollack
author: Subhash Suri
author: Sue Whitesides
author: Chee K. Yap
published in: Discrete \& Computational Geometry
publication date: 1988-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/131051
review text: The link center of a simple polygon \({\mathfrak P}\) is the set of points x inside \({\mathfrak P}\) at which the maximal link-distance from x to any other point in \({\mathfrak P}\) is minimized. Here the link distance between two points x, y inside \({\mathfrak P}\) is defined to be the smallest number of straight edges in a polygonal path inside \({\mathfrak P}\) connecting x to y. We prove several geometric properties of the link center and present an algorithm that calculates this set in time \(O(n^ 2)\), where n is the number of sides of \({\mathfrak P}\). We also give an O(n log n) algorithm for finding an approximate link center, that is, a point x such that the maximal link distance from x to any point in \({\mathfrak P}\) is at most one more than the value attained from the true link center.
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4055042
zbMATH Keywords: link geodesics
zbMATH Keywords: visibility
zbMATH Keywords: computational geometry
zbMATH Keywords: simple polygon
zbMATH Keywords: approximate link center
MaRDI profile type: Publication
Wikidata QID: Q62037524
cites work: Q3787491
cites work: Visibility and intersection problems in plane geometry
cites work: A linear algorithm for computing the visibility polygon from a point
cites work: Triangulating a simple polygon
cites work: Q3328583
cites work: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
cites work: Euclidean shortest paths in the presence of rectilinear barriers
cites work: Q3290331
cites work: Computing the geodesic center of a simple polygon
cites work: Erratum: An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
OpenAlex ID: W4299815227
description: scientific article; zbMATH DE number 4055042