Search Constraints

Start Over
Filtering by: Creator Davoodi, Pooya Remove constraint Creator: Davoodi, Pooya Creator Smid, Michiel Remove constraint Creator: Smid, Michiel

Search Results

  • Two-dimensional range diameter queries

    Resource Type:
    Conference Proceeding
    Creator:
    Van Walderveen, Freek, Davoodi, Pooya, and Smid, Michiel
    Abstract:
    Given a set of n points in the plane, range diameter queries ask for the furthest pair of points in a given axis-parallel rectangular range. We provide evidence for the hardness of designing space-efficient data structures that support range diameter queries by giving a reduction from the set intersection problem. The difficulty of the latter problem is widely acknowledged and is conjectured to require nearly quadratic space in order to obtain constant query time, which is matched by known data structures for both problems, up to polylogarithmic factors. We strengthen the evidence by giving a lower bound for an important subproblem arising in solutions to the range diameter problem: computing the diameter of two convex polygons, that are separated by a vertical line and are preprocessed independently, requires almost linear time in the number of vertices of the smaller polygon, no matter how much space is used. We also show that range diameter queries can be answered much more efficiently for the case of points in convex position by describing a data structure of size O(n log n) that supports queries in O(log n) time.
    Date Created:
    2012-05-15