We propose an algorithm to compute and maintain the spatial proximities of
planar points continuously moving along predened linear trajectories. The proximity information of moving points is captured and maintained via the well known Gabriel graph
adapted for the kinetic setting, called kinetic Gabriel graph (KGG). Kinetic Gabriel Graph
is built on top of the kinetic framework of Delaunay graph. Leveraging the positioning of
the Delaunay circumcenters relative to the corresponding Delaunay triangles, we formulate
`Gabriel certicates' that determine whether or not an edge of a Delaunay triangle is Gabriel.
Then we employ an edge tagging algorithm to maintain the set of all Gabriel edges from
the Delaunay graph as the points move. The proposed algorithm has been evaluated using
numerous test data, and various computational implications with respect to the topological
events occurring in the data structure during the points' movement have been discussed. We
also provide a conceptual demonstration of the practical potentials of the proposed algorithm
in video based monitoring systems.
|Journal||Computer-Aided Design & Applications|
|Publisher||CAD Solutions, LLC|