Article Preview
TopIntroduction
Kinetic data structures (Basch, 1999; Basch, Guibas, & Hershberger, 1997; L. J. Guibas, 1998) are a class of geometric data structures used to represent moving objects, which are objects in continuous motion. Unsurprisingly, such data structures have many applications in robotics for collision detection and collision avoidance, a sub-discipline of Artificial Intelligence (Russell, Norvig, & Intelligence 1995). Robotics includes intelligent control as a sub-area of research. Some of the other applications of kinetic data structures are in motion planning, computer graphics such as games, animation, mesh generation, traffic control, transaction time databases etc. Computational geometry (de Berg, Cheong, Kreveld, & Overmars, 2008; Preparata & Shamos, 1985) offers solutions to such problems by considering the objects depending on their respective shapes such as points, lines, etc. Normally, a geometric data structure such as kd-trees are used to store point data and segment trees are used to store line segments in these problems. In this work, we consider line segments representing a robot or a vehicle. The primary goal is to design a kinetic data structure that requires fewer updates to the data structure during an event, and this actually determines the efficiency of the data structure. Kinetic segment trees (de Berg et al., 2001) have realized an O(log n) time and the running time has to be reduced further. The best-known application of a KDS is maintaining a convex hull on a set of moving points (Abam & de Berg, 2005; Basch, Guibas, & Zhang, 1997). Recently, nearest neighbours of points are found using kinetic triangulation as a KDS for mesh refinement (Acar, Hudson, & Turkoglu, 2011; Kaplan, Rubin, & Sharir, 2011).