Computing the geodesic center of a simple polygon

DOI10.1007/BF02187751zbMATH Open0689.68067MaRDI QIDQ582099FDOQ582099

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

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

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)

Cites Work

• Linear Programming in Linear Time When the Dimension Is Fixed
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Euclidean shortest paths in the presence of rectilinear barriers
• On the ball spanned by balls
• Title not available (Why is that?)
• Computing the geodesic center of a simple polygon
• Triangulating a simple polygon
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
• Computing the link center of a simple polygon
• 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

Cited In (48)

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

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)