Computing Motorcycle Graphs Based on Kinetic Triangulations
Willi Mann, Martin Held, Stefan G. Huber · 2012
We present an efficient algorithm for computing general-ized motorcycle graphs, in which motorcycles are allowed to emerge after time zero. Our algorithm applies kinetic triangulations inside of the convex hull of the input, while a plane sweep is used outside of it. Its worst-case com-plexity is O((n + f) log n), where f ∈ O(n3) denotes the number of flip events that occur in the kinetic triangu-lation. Outside of the convex hull it runs in O(n log n) time. In order to reduce the number of flip events we investigate the use of Steiner triangulations. We prove the existence of Steiner triangulations that eliminate all flip events and discuss heuristics for approximating such a Steiner triangulation. Extensive experiments with our C++ implementation run on thousands of datasets of various characteristics demonstrate a runtime of c · 10−6 · n log n seconds, with c ≤ 4 for virtually all of our datasets. This constitutes a significant practical improvement over the motorcycle code Moca [Huber&Held 2011], which runs in O(n log n) time only if the motorcycles are distributed uniformly enough. In particular, our experiments yielded f ≤ 5n flip events for all but very few datasets.