Computing the link center of a simple polygon

DOI10.1007/BF02187913MaRDI QIDQ1104086zbMATH OpenOpenAlexWikidataFDO

Authors Jörg-Rüdiger Sack, Raimund Seidel, Micha Sharir, Godfried Toussaint, William Lenhart, Richard Pollack, Subhash Suri, Sue Whitesides, Chee K. Yap

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

computational geometryvisibilitysimple polygonapproximate link centerlink geodesics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• 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

Cites work

• 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?)
• 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
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Triangulating a simple polygon
• Visibility and intersection problems in plane geometry

Cited in

(24)

• 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 constrained Euclidean, geodesic and link centre of a simple polygon with applications.
• On the geodesic Voronoi diagram of point sites in a simple polygon
• Geodesic convexity in discrete spaces
• Minimal link visibility paths inside a simple polygon
• An \(O(n\log n)\) algorithm for computing the link center of a simple polygon
• Visibility with multiple diffuse reflections
• An optimal algorithm for the rectilinear link center of a rectilinear polygon
• Helly-gap of a graph and vertex eccentricities
• Rectilinear paths among rectilinear obstacles
• Settling the bound on the rectilinear link radius of a simple rectilinear polygon
• On the polygonal diameter (= link diameter) of the interior, resp. exterior, of a simple closed polygon in the plane
• Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric
• Optimal parallel algorithms for rectilinear link-distance problems
• Optimal on-line algorithms for walking with minimum number of turns in unknown streets
• An O(n log n) ALGORITHM FOR FINDING A SHORTEST CENTRAL LINK SEGMENT
• Diffuse reflection diameter and radius for convex-quadrilateralizable polygons
• Connect the Dot: Computing Feed-Links with Minimum Dilation
• Minimum-link paths among obstacles in the plane
• On rectilinear link distance
• Computing the geodesic center of a simple polygon
• Efficient piecewise-linear function approximation using the uniform metric
• Computing the L 1-diameter and center of a simple rectilinear polygon in parallel

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)