Computing the link center of a simple polygon

DOI10.1007/BF02187913zbMath0646.68056OpenAlexW4299815227WikidataQ62037524 ScholiaQ62037524MaRDI QIDQ1104086

Jörg-Rüdiger Sack, Godfried T. Toussaint, Micha Sharir, Raimund Seidel, Richard Pollack, Chee-Keng Yap, Subhash Suri, William J. Lenhart, S. H. Whitesides

Publication date: 1988

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131051

zbMATH Keywords

visibilitycomputational geometrysimple polygonapproximate link centerlink geodesics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (23)

Minimal link visibility paths inside a simple polygon ⋮ Geodesic convexity in discrete spaces ⋮ 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 ⋮ Optimal parallel algorithms for rectilinear link-distance problems ⋮ Efficient piecewise-linear function approximation using the uniform metric ⋮ Optimal on-line algorithms for walking with minimum number of turns in unknown streets ⋮ On the geodesic Voronoi diagram of point sites in a simple polygon ⋮ An optimal algorithm for the rectilinear link center of a rectilinear polygon ⋮ Helly-gap of a graph and vertex eccentricities ⋮ An O(n log n) algorithm for computing a link center in a simple polygon ⋮ Visibility with multiple diffuse reflections ⋮ Settling the bound on the rectilinear link radius of a simple rectilinear 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 ⋮ An \(O(n\log n)\) algorithm for computing the link center of a simple polygon ⋮ Minimum-link paths among obstacles in the plane ⋮ An O(n log n) ALGORITHM FOR FINDING A SHORTEST CENTRAL LINK SEGMENT ⋮ Computing the geodesic center of a simple polygon ⋮ Diffuse reflection radius in a simple polygon ⋮ Rectilinear paths among rectilinear obstacles ⋮ On rectilinear link distance

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the geodesic center of a simple polygon
• Visibility and intersection problems in plane geometry
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Triangulating a simple polygon
• Euclidean shortest paths in the presence of rectilinear barriers
• Erratum: An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
• A linear algorithm for computing the visibility polygon from a point

This page was built for publication: Computing the link center of a simple polygon