Search Constraints

Start Over
Filtering by: Creator Morin, Pat Remove constraint Creator: Morin, Pat

Search Results

  • A generalized Winternitz Theorem

    Resource Type:
    Article
    Creator:
    Morin, Pat, Hurtado, Ferran, Bose, Prosenjit, and Carmi, Paz
    Abstract:
    We prove that, for every simple polygon P having k ≥ 1 reflex vertices, there exists a point q ε P such that every half-polygon that contains q contains nearly 1/2(k + 1) times the area of P. We also give a family of examples showing that this result is the best possible.
    Date Created:
    2011-04-01

  • Online routing in triangulations?

    Resource Type:
    Conference Proceeding
    Creator:
    Morin, Pat and Bose, Prosenjit
    Abstract:
    We consider online routing strategies for routing between the vertices of embedded planar straight line graphs. Our results include (1) two deterministic memoryless routing strategies, one that works for all Delaunay triangulations and the other that works for all regular triangulations, (2) a randomized memoryless strategy that works for all triangulations, (3) an O(1) memory strategy that works for all convex subdivisions, (4) an O(1) memory strategy that approximates the shortest path in Delaunay triangulations, and (5) theoretical and experimental results on the competitiveness of these strategies.
    Date Created:
    1999-01-01

  • Randomized rendez-vous with limited memory

    Resource Type:
    Conference Proceeding
    Creator:
    Kranakis, Evangelos, Morin, Pat, and Krizanc, Danny
    Abstract:
    We present a tradeoff between the expected time for two identical agents to rendez-vous on a synchronous, anonymous, oriented ring and the memory requirements of the agents. In particular, we show that there exists a 2t state agent, which can achieve rendez-vous on an n node ring in expected time O( n 2/2 t ∈+∈2 t ) and that any t/2 state agent requires expected time Ω( n 2/2 t ). As a corollary we observe that Θ(loglogn) bits of memory are necessary and sufficient to achieve rendez-vous in linear time.
    Date Created:
    2008-05-12

  • A distribution-sensitive dictionary with low space overhead

    Resource Type:
    Conference Proceeding
    Creator:
    Bose, Prosenjit, Howat, John, and Morin, Pat
    Abstract:
    The time required for a sequence of operations on a data structure is usually measured in terms of the worst possible such sequence. This, however, is often an overestimate of the actual time required. Distribution-sensitive data structures attempt to take advantage of underlying patterns in a sequence of operations in order to reduce time complexity, since access patterns are non-random in many applications. Unfortunately, many of the distribution- sensitive structures in the literature require a great deal of space overhead in the form of pointers. We present a dictionary data structure that makes use of both randomization and existing space-efficient data structures to yield very low space overhead while maintaining distribution sensitivity in the expected sense.
    Date Created:
    2009-09-14

  • Succinct orthogonal range search structures on a grid with applications to text indexing

    Resource Type:
    Conference Proceeding
    Creator:
    Bose, Prosenjit, Maheshwari, Anil, He, Meng, and Morin, Pat
    Abstract:
    We present a succinct representation of a set of n points on an n×n grid using bits to support orthogonal range counting in time, and range reporting in time, where k is the size of the output. This achieves an improvement on query time by a factor of upon the previous result of Mäkinen and Navarro [1], while using essentially the information-theoretic minimum space. Our data structure not only can be used as a key component in solutions to the general orthogonal range search problem to save storage cost, but also has applications in text indexing. In particular, we apply it to improve two previous space-efficient text indexes that support substring search [2] and position-restricted substring search [1]. We also use it to extend previous results on succinct representations of sequences of small integers, and to design succinct data structures supporting certain types of orthogonal range query in the plane.
    Date Created:
    2009-09-14