Computing the geodesic center of a simple polygon
From MaRDI portal
Publication:582099
DOI10.1007/BF02187751zbMath0689.68067MaRDI QIDQ582099
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
Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Convex sets in (2) dimensions (including convex curves) (52A10)
Related Items
Packing and covering with balls on Busemann surfaces, The geodesic 2-center problem in a simple polygon, Computing the geodesic centers of a polygonal domain, Computing the L 1-diameter and center of a simple rectilinear polygon in parallel, Computing the link center of a simple polygon, The polygon burning problem, On the geodesic Voronoi diagram of point sites in a simple polygon, The geodesic diameter of polygonal domains, An O(n log n) algorithm for computing a link center in a simple polygon, Kinetic Geodesic Voronoi Diagrams in a Simple Polygon, Clique-based separators for geometric intersection graphs, An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons, Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon, SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS, Computing external farthest neighbors for a simple polygon, Blaschke-type theorem and separation of disjoint closed geodesic convex sets, Piercing pairwise intersecting geodesic disks, An \(O(n\log n)\) algorithm for computing the link center of a simple polygon, GEODESIC DISKS AND CLUSTERING IN A SIMPLE POLYGON, Computing the \(L_1\) geodesic diameter and center of a polygonal domain, Some Computational Aspects of Geodesic Convex Sets in a Simple Polygon, The furthest-site geodesic Voronoi diagram, Unnamed Item, Computing the geodesic center of a simple polygon, Computing the external geodesic diameter of a simple polygon, Diffuse reflection radius in a simple polygon, A linear-time algorithm for the geodesic center of a simple polygon, PARETO ENVELOPES IN SIMPLE POLYGONS, Voronoi diagrams for a moderate-sized point-set in a simple polygon, On the ball spanned by balls, The geodesic farthest-point Voronoi diagram in a simple polygon, Multiple-guard kernels of simple polygons, Computing geodesic furthest neighbors in simple polygons, Centers of sets of pixels, Computing a geodesic two-center of points in a simple polygon, Piercing pairwise intersecting geodesic disks by five points, Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time
Cites Work
- Unnamed Item
- Computing the geodesic center of a simple polygon
- An O(n) algorithm for the linear multiple choice knapsack problem and related problems
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Computing the link center of a simple polygon
- Triangulating a simple polygon
- On the ball spanned by balls
- Linear Time Algorithms for Two- and Three-Variable Linear Programs
- Euclidean shortest paths in the presence of rectilinear barriers
- Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
- Linear Programming in Linear Time When the Dimension Is Fixed
- On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
