A faster algorithm for computing motorcycle graphs

DOI10.1007/s00454-014-9625-2zbMath1302.68296arXiv1303.5958OpenAlexW2086828419MaRDI QIDQ471142

Lie Yan, Antoine Vigneron

Publication date: 14 November 2014

Published in: Discrete \& Computational Geometry, Proceedings of the twenty-ninth annual symposium on Computational geometry (Search for Journal in Brave)

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

zbMATH Keywords

polygoncomputational geometrymedial axisstraight skeletonalgorithms design and analysismotorcycle graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Straight skeletons and mitered offsets of nonconvex polytopes ⋮ Computing positively weighted straight skeletons of simple polygons based on a bisector arrangement ⋮ A simple algorithm for computing positively weighted straight skeletons of monotone polygons ⋮ Implementing straight skeletons with exact arithmetic: challenges and experiences

Uses Software

• Moca

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal partition trees
• Motorcycle graphs and straight skeletons
• Applications of a new space-partitioning technique
• Efficient partition trees
• Ray shooting in polygons using geodesic triangulations
• Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions
• On Computing Straight Skeletons by Means of Kinetic Triangulations
• Delaunay triangulations in O (sort( n )) time and more
• Dynamic Ray Shooting and Shortest Paths in Planar Subdivisions via Balanced Geodesic Triangulations
• Ray Shooting and Parametric Search
• Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time
• Ray Shooting Amidst Convex Polygons in 2D
• New Results on Dynamic Planar Point Location
• A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
• A FAST STRAIGHT-SKELETON ALGORITHM BASED ON GENERALIZED MOTORCYCLE GRAPHS
• Motorcycle graphs

This page was built for publication: A faster algorithm for computing motorcycle graphs