An Efficient Kinetic Range Query for One Dimensional Axis Parallel Segments

An Efficient Kinetic Range Query for One Dimensional Axis Parallel Segments

T. Hema (Anna University, Department of Computer Science and Engineering, Chennai, India) and K. S. Easwarakumar (Anna University, Department of Computer Science and Engineering, Chennai, India)
Copyright: © 2018 |Pages: 15
DOI: 10.4018/IJIIT.2018010104
OnDemand PDF Download:
No Current Special Offers


We present a kinetic data structure named Kinetic Interval Graph (KI-Graph) for performing efficient range search on moving one dimensional axis-parallel segments. This finds applications in Artificial Intelligence such as robotic motion. The structure requires O(n) storage. The time taken per update when a critical event occurs is O (1) thereby improving responsiveness when compared to the kinetic segment trees, while the overall updates across all segments at a time instance is at most n/2. Also, range query is performed efficiently in θ (k) time, where k segments are reported.
Article Preview


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).

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 18: 4 Issues (2022): 2 Released, 2 Forthcoming
Volume 17: 4 Issues (2021)
Volume 16: 4 Issues (2020)
Volume 15: 4 Issues (2019)
Volume 14: 4 Issues (2018)
Volume 13: 4 Issues (2017)
Volume 12: 4 Issues (2016)
Volume 11: 4 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing