Dynamic computational geometry on meshes and hypercubes |
| |
| Authors: | Laurence Boxer Russ Miller |
| |
| Affiliation: | (1) Department of Computer and Information Sciences, Niagara University, 14109, NY, USA;(2) Department of Computer Science, State University of New York, 14260 Buffalo, NY, USA |
| |
| Abstract: | Parallel algorithms are given for determining geometric properties of systems of moving point-objects. The objects are assumed to be moving in a Euclidean space such that each coordinate of a point's motion is a polynomial of bounded degree in the time variable. The properties investigated include nearest (farthest) neighbor, closest (farthest) pair, collision, convex hull, diameter, and containment. Several of these properties are investigated from both the dynamic and steady-state points of view. Efficient, and often optimal, implementations of these algorithms are given for the mesh and hypercube.Research partially supported by a grant from the Niagara University Research Council.Research partially supported by National Science Foundation grants DCR-8608640 and IRI-8800514. |
| |
| Keywords: | mesh hypercube dynamic computational geometry parallel algorithms nearest neighbor closest pair convex hull smallest enclosing rectangle |
| 本文献已被 SpringerLink 等数据库收录！ |
|
