Home

Pat Morin

  1. Approximating Majority Depth.

    Wed, 05/09/2012 - 15:01 — SomNambul
    Authors: Pat Morin, Dan Chen
    Subjects: Computational Geometry
    Abstract

    We consider the problem of approximating the majority depth (Liu and Singh,
    1993) of a point q with respect to an n-point set, S, by random sampling. At
    the heart of this problem is a data structures question: How can we preprocess
    a set of n lines so that we can quickly test whether a randomly selected vertex
    in the arrangement of these lines is above or below the median level. We
    describe a Monte-Carlo data structure for this problem that can be constructed
    in O(nlog n$ time, can answer queries O((log n)^{4/3}) expected time, and
    answers correctly with high probability.

  2. A Tight Bound on the Maximum Interference of Random Sensors in the Highway Model.

    Wed, 07/14/2010 - 15:02 — SomNambul
    Authors: Pat Morin, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Ladislav Stacho
    Subjects: Computational Geometry
    Abstract

    Consider $n$ sensors whose positions are represented by $n$ uniform,
    independent and identically distributed random variables assuming values in the
    open unit interval $(0,1)$. A natural way to guarantee connectivity in the
    resulting sensor network is to assign to each sensor as its range, the maximum
    of the two possible distances to its two neighbors. The interference at a given
    sensor is defined as the number of sensors that have this sensor within their
    range. In this paper we prove that the expected maximum interference of the
    sensors is $\Theta (\sqrt{\ln n})$.

  3. Odds-On Trees.

    Mon, 02/08/2010 - 16:01 — SomNambul
    Authors: Luc Devroye, Vida Dujmovic, Pat Morin, Prosenjit Bose, Karim Douieb, James King
    Subjects: Computational Geometry
    Abstract

    Let R^d -> A be a query problem over R^d for which there exists a data
    structure S that can compute P(q) in O(log n) time for any query point q in
    R^d. Let D be a probability measure over R^d representing a distribution of
    queries. We describe a data structure called the odds-on tree, of size
    O(n^\epsilon) that can be used as a filter that quickly computes P(q) for some
    query values q in R^d and relies on S for the remaining queries.

  4. Planar Visibility: Testing and Counting.

    Mon, 01/18/2010 - 16:01 — SomNambul
    Authors: Joachim Gudmundsson, Pat Morin
    Subjects: Computational Geometry
    Abstract

    In this paper we consider query versions of visibility testing and visibility
    counting. Let $S$ be a set of $n$ disjoint line segments in $\R^2$ and let $s$
    be an element of $S$. Visibility testing is to preprocess $S$ so that we can
    quickly determine if $s$ is visible from a query point $q$. Visibility counting
    involves preprocessing $S$ so that one can quickly estimate the number of
    segments in $S$ visible from a query point $q$.

  5. Point Location in Disconnected Planar Subdivisions.

    Mon, 01/18/2010 - 16:01 — SomNambul
    Authors: Luc Devroye, Vida Dujmovic, Pat Morin, Prosenjit Bose, Karim Douieb, James King
    Subjects: Computational Geometry
    Abstract

    Let $G$ be a (possibly disconnected) planar subdivision and let $D$ be a
    probability measure over $\R^2$. The current paper shows how to preprocess
    $(G,D)$ into an O(n) size data structure that can answer planar point location
    queries over $G$. The expected query time of this data structure, for a query
    point drawn according to $D$, is $O(H+1)$, where $H$ is a lower bound on the
    expected query time of any linear decision tree for point location in $G$. This
    extends the results of Collette et al (2008, 2009) from connected planar
    subdivisions to disconnected planar subdivisions.

  6. Memoryless Routing in Convex Subdivisions: Random Walks are Optimal.

    Mon, 11/16/2009 - 16:01 — SomNambul
    Authors: Luc Devroye, Vida Dujmovic, Pat Morin, Dan Chen
    Subjects: Computational Geometry
    Abstract

    A memoryless routing algorithm is one in which the decision about the next
    edge on the route to a vertex t for a packet currently located at vertex v is
    made based only on the coordinates of v, t, and the neighbourhood, N(v), of v.
    The current paper explores the limitations of such algorithms by showing that,
    for any (randomized) memoryless routing algorithm A, there exists a convex
    subdivision on which A takes Omega(n^2) expected time to route a message
    between some pair of vertices.

  7. Notes on large angle crossing graphs.

    Wed, 08/26/2009 - 14:59 — SomNambul
    Authors: Vida Dujmovic, Joachim Gudmundsson, Pat Morin, Thomas Wolle
    Subjects: Data Structures and Algorithms
    Abstract

    A graph G is an a-angle crossing (aAC) graph if every pair of crossing edges
    in G intersect at an angle of at least a. The concept of right angle crossing
    (RAC) graphs (a=Pi/2) was recently introduced by Didimo et. al. It was shown
    that any RAC graph with n vertices has at most 4n-10 edges and that there are
    infinitely many values of n for which there exists a RAC graph with n vertices
    and 4n-10 edges. In this paper, we give upper and lower bounds for the number
    of edges in aAC graphs for all 0 < a < Pi/2.

Math-arch

Syndicate content