Kinetic Data Structures

Authored by: Leonidas Guibas

Handbook of Data Structures and Applications

Print publication date:  March  2018
Online publication date:  February  2018

Print ISBN: 9781498701853
eBook ISBN: 9781315119335
Adobe ISBN:


 Download Chapter



Motion is ubiquitous in the physical world, yet its study is much less developed than that of another common physical modality, namely shape. While we have several standardized mathematical shape descriptions, and even entire disciplines devoted to that area—such as Computer-Aided Geometric Design (CAGD)—the state of formal motion descriptions is still in flux. This in part because motion descriptions span many levels of detail; they also tend to be intimately coupled to an underlying physical process generating the motion (dynamics). Thus, until recently, proper abstractions were lacking and there was only limited work on algorithmic descriptions of motion and their associated complexity measures. This chapter aims to show how an algorithmic study of motion is intimately tied via appropriate data structures to more classical theoretical disciplines, such as discrete and computational geometry. After a quick survey of earlier work (Sections 24.2 and 24.3), we devote the bulk of this chapter to discussing the framework of Kinetic Data Structures (Section 24.4) [1,2] and its many applications (Section 24.5). We also briefly discuss methods for querying moving objects (Section 24.6).

Search for more...
Back to top

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.