Point location

From: Thomas Heinz (thomasheinz_at_gmx.net)
Date: 03/22/05

  • Next message: Paul E. Black: "Re: Point location" 
    Date: Tue, 22 Mar 2005 18:29:10 +0100

    Hi

    The following problem is a special case of the so-called point
    location problem [computational model: RAM].

    Let S be a set of n axis aligned orthotopes (generalization of
    rectangle, hyper-rectangle) in d-dimensional space such that
    no two orthotopes overlap each other. Given a point, the
    problem is to determine the orthotope in S containing the point
    if any.

    - What is the minimal worst case space complexity of known
       algorithms with O(log n) query time?
    - What is the minimal worst case query time of known
       algorithms with linear or almost linear worst case space
       complexity, e.g. O(n^(1 + epsilon))
    - Is O(log n) query time using (almost) linear space possible?
    - In general, what are the "best known" algorithms for this
       problem?
    - Are any space/time lower bounds known?
    - Are there any randomized algorithms beating deterministic
       ones when comparing expected worst case bounds with worst
       case bounds of efficient deterministic algorithms?

    Thanks for your help.

    Regards,

    Thomas

  • Next message: Paul E. Black: "Re: Point location"