Computing the link center of a simple polygon
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.
- An \(O(n\log n)\) algorithm for computing the link center of a simple polygon
- Computing the constrained Euclidean, geodesic and link centre of a simple polygon with applications.
- An O(n n) algorithm for computing a link center in a simple polygon
- An optimal algorithm for the rectilinear link center of a rectilinear polygon
- scientific article; zbMATH DE number 4051002
- A linear algorithm for computing the visibility polygon from a point
- Computing the geodesic center of a simple polygon
- Erratum: An O(n\log \log n)-Time Algorithm for Triangulating a Simple Polygon
- Euclidean shortest paths in the presence of rectilinear barriers
- scientific article; zbMATH DE number 3171651 (Why is no real title available?)
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 4051002 (Why is no real title available?)
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Triangulating a simple polygon
- Visibility and intersection problems in plane geometry
- On the geodesic Voronoi diagram of point sites in a simple polygon
- An \(O(n\log n)\) algorithm for computing the link center of a simple polygon
- Minimum-link paths among obstacles in the plane
- Geodesic convexity in discrete spaces
- Optimal on-line algorithms for walking with minimum number of turns in unknown streets
- Visibility with multiple diffuse reflections
- Optimal parallel algorithms for rectilinear link-distance problems
- Efficient piecewise-linear function approximation using the uniform metric
- An optimal algorithm for the rectilinear link center of a rectilinear polygon
- Settling the bound on the rectilinear link radius of a simple rectilinear polygon
- Minimal link visibility paths inside a simple polygon
- Diffuse reflection diameter and radius for convex-quadrilateralizable polygons
- On the polygonal diameter (= link diameter) of the interior, resp. exterior, of a simple closed polygon in the plane
- Rectilinear paths among rectilinear obstacles
- Helly-gap of a graph and vertex eccentricities
- Computing the constrained Euclidean, geodesic and link centre of a simple polygon with applications.
- Connect the Dot: Computing Feed-Links with Minimum Dilation
- An O(n log n) ALGORITHM FOR FINDING A SHORTEST CENTRAL LINK SEGMENT
- Computing the L 1-diameter and center of a simple rectilinear polygon in parallel
- Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric
- Parallel algorithms for all minimum link paths and link center problems
- An O(n n) algorithm for computing a link center in a simple polygon
- Computing the geodesic center of a simple polygon
- On rectilinear link distance
This page was built for publication: Computing the link center of a simple polygon
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104086)
