Accueil

Joachim Gudmundsson

  1. Quickest Path Queries on Transportation Network.

    Mon, 12/06/2010 - 16:01 — SomNambul
    Authors: Joachim Gudmundsson, Radwa El Shawi, Christos Levcopoulos
    Subjects: Computational Geometry
    Abstract

    This paper considers the problem of finding a quickest path between two
    points in the Euclidean plane in the presence of a transportation network. A
    transportation network consists of a planar network where each road (edge) has
    an individual speed. A traveller may enter and exit the network at any point on
    the roads. Along any road the traveller moves with a fixed speed depending on
    the road, and outside the network the traveller moves at unit speed in any
    direction.

  2. Farthest-Polygon Voronoi Diagrams.

    Thu, 01/21/2010 - 16:01 — SomNambul
    Authors: Joachim Gudmundsson, Otfried Cheong, Hazel Everett, Marc Glisse, Samuel Hornus, Sylvain Lazard, Mira Lee, Hyeon-Suk Na
    Subjects: Computational Geometry
    Abstract

    Given a family of k disjoint connected polygonal sites in general position
    and of total complexity n, we consider the farthest-site Voronoi diagram of
    these sites, where the distance to a site is the distance to a closest point on
    it. We show that the complexity of this diagram is O(n), and give an O(n log^3
    n) time algorithm to compute it. We also prove a number of structural
    properties of this diagram. In particular, a Voronoi region may consist of k-1
    connected components, but if one component is bounded, then it is equal to the
    entire region.

  3. 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$.

  4. 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