101. Motorcycle graphs and straight skeletons
- Author
-
Antoine Vigneron, Siu-Wing Cheng, Department of Computer Science, Hong Kong University of Science and Technology (HKUST), Unité de biométrie et intelligence artificielle de jouy, and Institut National de la Recherche Agronomique (INRA)
- Subjects
General Computer Science ,0102 computer and information sciences ,02 engineering and technology ,Computer Science::Computational Geometry ,Characterization (mathematics) ,Skeleton (category theory) ,01 natural sciences ,MOTORCYCLE GRAPH ,Combinatorics ,Medial axis ,0202 electrical engineering, electronic engineering, information engineering ,[INFO]Computer Science [cs] ,COMPUTATIONAL GEOMETRY ,[MATH]Mathematics [math] ,Mathematics ,GEOMETRIE ALGORITHMIQUE ,STRAIGHT SKELETON ,Straight skeleton ,Applied Mathematics ,MEDIAL AXIS ,020207 software engineering ,Binary logarithm ,Computational geometry ,Computer Science Applications ,Randomized algorithm ,010201 computation theory & mathematics ,Polygon ,RANDOMIZED ALGORITHM - Abstract
We present a new algorithm to compute motorcycle graphs. It runs in $O(n \sqrt{n}\log n)$ time when n is the number of motorcycles. We give a new characterization of the straight skeleton of a nondegenerate polygon. For a polygon with n vertices and h holes, we show that it yields a randomized algorithm that reduces the straight skeleton computation to a motorcycle graph computation in expected $O(n\sqrt{h+1}\log^2 n)$ time. Combining these results, we can compute the straight skeleton of a nondegenerate polygon with h holes and with n vertices, among which r are reflex vertices, in $O(n\sqrt{h+1}\log^2 n+r \sqrt{r} \log r)$ expected time. In particular, we cancompute the straight skeleton of a nondegenerate polygon with n vertices in $O(n\sqrt{n}\log^2n)$ expected time.