The geodesic edge center of a simple polygon

DOI10.1007/S00454-025-00768-9MaRDI QIDQ6878295zbMATH OpenFDO

Authors Anna Lubiw

Publication date 6 January 2026

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00454-025-00768-9

zbMATH Keywords

facility locationgeodesicsoptimizationshortest paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80)

Cites work

• -nets and simplex range queries
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• A linear-time algorithm for the geodesic center of a simple polygon
• An \(O(n\log n)\) algorithm for the all-farthest-segments problem for a planar set of points
• An Optimal Algorithm for the Intersection Radius of a Set of Convex Polygons
• An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons
• Approximations and optimal geometric divide-and-conquer
• Common tangents of two disjoint polygons in linear time and constant workspace
• Computing geodesic furthest neighbors in simple polygons
• Computing the geodesic center of a simple polygon
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Cutting hyperplane arrangements
• Cutting hyperplanes for divide-and-conquer
• Divide-and-conquer for Voronoi diagrams revisited
• Euclidean shortest paths in the presence of rectilinear barriers
• Farthest line segment Voronoi diagrams
• Farthest-polygon Voronoi diagrams
• Fast Algorithms for Finding Nearest Common Ancestors
• Finding the medial axis of a simple polygon in linear time
• Geometric applications of a matrix-searching algorithm
• Geometric approximation algorithms
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 6876082 (Why is no real title available?)
• scientific article; zbMATH DE number 7559212 (Why is no real title available?)
• 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
• Matrix Searching with the Shortest-Path Metric
• On the ball spanned by balls
• On the farthest line-segment Voronoi diagram
• Optimal algorithms for some intersection radius problems
• Optimal shortest path queries in a simple polygon
• Sampling in combinatorial and geometric set systems
• The furthest-site geodesic Voronoi diagram
• The geodesic edge center of a simple polygon
• The geodesic farthest-point Voronoi diagram in a simple polygon
• The Visibility Center of a Simple Polygon
• Visibility and intersection problems in plane geometry
• Voronoi diagrams and Delaunay triangulations
• Voronoi diagrams for a moderate-sized point-set in a simple polygon

This page was built for publication: The geodesic edge center of a simple polygon

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