| Many applications require the processing of moving objects. We concentrate on data management problems where an object is moving and we want to repeatedly answer queries about events throughout the motion. In particular we examine segment dragging queries, where a query segment is being translated across a collection of two-dimensional points. We also examine a generalization of segment dragging to three dimensions where a query plane moves across a collection of points. In both cases our algorithms report the points hit by the moving object in the order in which they are hit. We exploit the fact that the hit queries are related and therefore the information computed in answering one query can be used when answering the following one.; The focus of this thesis is to design algorithms that are not only efficient on theoretical computation models but are also efficient on real computer systems. We implemented our algorithms and provide empirical evidence to support the theoretical claims.; We apply our techniques to the problem of finding silhouettes of polyhedral models. We present the first non-trivial algorithm for solving this problem. We also examine several practical applications of our algorithm and present extensive experimental results.; We also provide a first implementation (to our knowledge) of the partition trees of Matousek. |
