Browsing by Author "Le, Thuy, T."

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    A dynamic data structure for efficient bounded line range search
    (2010) Le, Thuy, T.; Nickerson, Bradford, G.
    A dynamic data structure for efficient axis-aligned orthogonal range search on a set of n lines in a bounded plane is presented. The algorithm requires O(log n + k) time in the worst case to find all lines intersecting an axis aligned query rectangle R, for k the number of lines in range. O(n + lambda) space is required for the data structure used by the algorithm, where lambda is the number of intersection points among the lines. Insertion of a new rightmost line l or deletion of a leftmost line l requires O(n) time in the worst case. For a sparse arrangement of lines (i.e., for lambda = O(n)), insertion of a rightmost line l or deletion of a leftmost line l requires O (√n) expected time.
  • Thumbnail Image
    Item
    Graph Strip Tree for Efficient Search of Objects Moving on a Graph
    (2010) Le, Thuy, T.; Nickerson, Bradford, G.
    A spatio-temporal data structure to index objects moving at constant velocity on a graph is presented. It is designed to efficiently answer rectangle R plus time instance and time interval queries about the past positions of moving objects. Such data structures are useful, for example, when searching for vehicles moving on a road network in specific areas at specif times. Unlike other data structures that use Rtrees to index bounding boxes of moving object trajectories, our data structure represents moving objects as lines in a bounded space. For n moving object instances (unique entries of moving objects) on a graph with |E| edges, we show that O(log2 |E| + |L| x log2(n/|E|) + k) time is required to answer a rectangle R plus time interval query, for |L| the number of edges intersected by R and k the number of moving objects in range. Space O(n + k + |E|) is required to store n moving object instances with k intersections among them in |E| ordered polyline trees. Space Ω(n + |E|) is required to store the history of all n moving object instances.