Kinetic Geodesic Voronoi Diagrams in a Simple Polygon

DOI10.1137/20m1384804arXiv2002.05910OpenAlexW3005994687MaRDI QIDQ6057802

Matias Korman, André van Renssen, Frank Staals, Marcel Roeloffzen

Publication date: 26 October 2023

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2002.05910

zbMATH Keywords

computational geometrygeodesic distancesimple polygonkinetic data structuregeodesic Voronoi diagram

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the geodesic center of a simple polygon
• Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• On the geodesic Voronoi diagram of point sites in a simple polygon
• The furthest-site geodesic Voronoi diagram
• A new algorithm for shortest paths among obstacles in the plane
• A new approach for the geodesic Voronoi diagram of points in a simple polygon and other restricted polygonal domains
• Visibility queries and maintenance in simple polygons
• The geodesic 2-center problem in a simple polygon
• Computing the geodesic centers of a polygonal domain
• Visibility graphs, dismantlability, and the cops and robbers game
• A data structure for dynamic trees
• Realistic input models for geometric algorithms
• Voronoi diagrams for a moderate-sized point-set in a simple polygon
• Computing a geodesic two-center of points in a simple polygon
• On Kinetic Delaunay Triangulations
• A linear time algorithm for minimum link paths inside a simple polygon
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• Data Structures for Mobile Data
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Optimal Algorithm for Geodesic Nearest-point Voronoi Diagrams in Simple Polygons
• GEODESIC-PRESERVING POLYGON SIMPLIFICATION

This page was built for publication: Kinetic Geodesic Voronoi Diagrams in a Simple Polygon