Transactions of the Japan Society for Industrial and Applied Mathematics
Online ISSN : 2424-0982
ISSN-L : 0917-2246
Voronoi Diagram for Moving Points and its Applications
Keiko Imai
Author information
JOURNAL FREE ACCESS

1991 Volume 1 Issue 2 Pages 127-134

Details
Abstract
Recently, the Voronoi diagram for moving objects has been investigated in connection with motion planning in robotics and geometric optimization problems in computational geometry. In this paper, we consider the Voronoi diagram for moving points parametrized by t in the plane, whose coordinates are polynomials or rational functions of t. We show that the dynamic Voronoi diagram has the combinatorial complexity of O(n^2λ_<s+2>(n)) and can be computed in O(n^2λ_<s+1>(n)log n) time and O(n) space, where s is some fixed number and λ_s(n) is the maximum length of (n, s) Davenport-Schinzel sequence.
Content from these authors
© 1991 The Japan Society for Industrial and Applied Mathematics
Previous article Next article
feedback
Top