Computing the geodesic center of a simple polygon

DOI10.1007/BF02187751MaRDI QIDQ582099zbMATH OpenFDO

Authors Günter Rote, Micha Sharir, Richard Pollack

Publication date 1989

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

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

zbMATH Keywords

simple polygongeodesic center

Mathematics Subject Classification ID

Computing methodologies and applications (68U99) Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10)

Recommendations

• scientific article; zbMATH DE number 4051002
• Computing the geodesic centers of a polygonal domain
• A linear-time algorithm for the geodesic center of a simple polygon
• scientific article; zbMATH DE number 6789192
• Geodesic center of a simple polygon using a logarithmic number of extra variables
• Computing the link center of a simple polygon
• Computing the external geodesic diameter of a simple polygon
• The geodesic 2-center problem in a simple polygon

Cites work

• scientific article; zbMATH DE number 4051002 (Why is no real title available?)
• An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Computing the geodesic center of a simple polygon
• Computing the link center of a simple polygon
• Euclidean shortest paths in the presence of rectilinear barriers
• Linear Programming in Linear Time When the Dimension Is Fixed
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
• On the ball spanned by balls
• Triangulating a simple polygon

Cited in

(48)

• The geodesic farthest-point Voronoi diagram in a simple polygon
• The furthest-site geodesic Voronoi diagram
• The 2-center problem in a simple polygon
• Piercing pairwise intersecting geodesic disks
• Geodesic Disks and Clustering in a Simple Polygon
• Geodesic Fréchet distance inside a simple polygon
• Some computational aspects of geodesic convex sets in a simple polygon
• An \(O(n \log 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
• Computing the geodesic centers of a polygonal domain
• Computing geodesic furthest neighbors in simple polygons
• Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
• Voronoi diagrams for a moderate-sized point-set in a simple polygon
• Computing the external geodesic diameter of a simple polygon
• A linear-time algorithm for the geodesic center of a simple polygon
• scientific article; zbMATH DE number 140467 (Why is no real title available?)
• Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time
• Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon
• Computing the link center of a simple polygon
• An \(O(n\log n)\) algorithm for computing the link center of a simple polygon
• Approximation algorithms for the two-watchman route in a simple polygon
• The polygon burning problem
• Constrained geodesic centers of a simple polygon
• The geodesic 2-center problem in a simple polygon
• The Visibility Center of a Simple Polygon
• The geodesic edge center of a simple polygon
• Packing and covering with balls on Busemann surfaces
• Computing external farthest neighbors for a simple polygon
• Geodesic center of a simple polygon using a logarithmic number of extra variables
• On flipping the Fréchet distance
• SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS
• On the ball spanned by balls
• scientific article; zbMATH DE number 4051002 (Why is no real title available?)
• Multiple-guard kernels of simple polygons
• scientific article; zbMATH DE number 7559212 (Why is no real title available?)
• Pareto envelopes in simple polygons
• The geodesic diameter of polygonal domains
• Clique-based separators for geometric intersection graphs
• Blaschke-type theorem and separation of disjoint closed geodesic convex sets
• Centers of sets of pixels
• Computing the geodesic center of a simple polygon
• Geodesic disks and clustering in a simple polygon
• An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons
• Computing the L 1-diameter and center of a simple rectilinear polygon in parallel
• scientific article; zbMATH DE number 6789192 (Why is no real title available?)
• Piercing pairwise intersecting geodesic disks by five points
• Computing the \(L_1\) geodesic diameter and center of a polygonal domain

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q582099)