Algorithms for Dynamic Computational Geometry with Applications
Laurence Boxer
*
Department of Computer and Information Sciences, Niagara University, Niagara University, NY 14109, USA and Department of Computer Science and Engineering, State University of New York at Buffalo, USA.
*Author to whom correspondence should be addressed.
Abstract
Most of the literature of computational geometry concerns geometric properties of sets of static points. M.J. Atallah introduced “dynamic computational geometry,” concerned with both momentary and long-term geometric properties of sets of moving point-objects. This area of research seems to have been dormant recently. The current paper examines new problems in dynamic computational geometry: the “Too Close,” “Too Far,” and “3 Aligned” problems. Worst-case optimal solutions are given for these problems using the sequential and coarse-grained multicomputer (CGM) models of computation.
Keywords: Dynamic computational geometry, piecewise defined continuous function, analysis of algorithms, coarse-grained multicomputer