Thomas Wolle
The directed Hausdorff distance between imprecise point sets.
Mon, 09/28/2009 - 15:24 — SomNambulAuthors: Thomas Wolle, Christian Knauer, Maarten Löffler, Marc Scherfenberg
Subjects: Computational Geometry
AbstractWe consider the directed Hausdorff distance between point sets in the plane,
where one or both point sets consist of imprecise points. An imprecise point is
modelled by a disc given by its centre and a radius. The actual position of an
imprecise point may be anywhere within its disc. Due to the direction of the
Hausdorff Distance and whether its tight upper or lower bound is computed there
are several cases to consider. For every case we either show that the
computation is NP-hard or we present an algorithm with a polynomial running
time.Notes on large angle crossing graphs.
Wed, 08/26/2009 - 14:59 — SomNambulAuthors: Vida Dujmovic, Joachim Gudmundsson, Pat Morin, Thomas Wolle
Subjects: Data Structures and Algorithms
AbstractA 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.
User login
