Source author record

Joachim Gudmundsson

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Discrete Mathematics Artificial Intelligence Computer Science and Game Theory Computer Vision Graphics Information Retrieval Machine Learning math.CO math.MG Multiagent Systems

Catalog footprint

Research overview

17works

12topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Covering a set of line segments with a few squares

We study three covering problems in the plane. Our original motivation for these problems come from trajectory analysis. The first is to decide whether a given set of line segments can be covered by up to four unit-sized, axis-parallel squares. The second is to build a data structure on a trajectory to efficiently answer whether any query subtrajectory is coverable by up to three unit-sized axis-parallel squares. The third problem is to compute a longest subtrajectory of a given trajectory that can be covered by up to two unit-sized axis-parallel squares.

preprint2022arXiv

Exploring Sub-skeleton Trajectories for Interpretable Recognition of Sign Language

Recent advances in tracking sensors and pose estimation software enable smart systems to use trajectories of skeleton joint locations for supervised learning. We study the problem of accurately recognizing sign language words, which is key to narrowing the communication gap between hard and non-hard of hearing people. Our method explores a geometric feature space that we call `sub-skeleton' aspects of movement. We assess similarity of feature space trajectories using natural, speed invariant distance measures, which enables clear and insightful nearest neighbor classification. The simplicity and scalability of our basic method allows for immediate application in different data domains with little to no parameter tuning. We demonstrate the effectiveness of our basic method, and a boosted variation, with experiments on data from different application domains and tracking technologies. Surprisingly, our simple methods improve sign recognition over recent, state-of-the-art approaches.

preprint2022arXiv

Local Routing in Sparse and Lightweight Geometric Graphs

Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no $O(1)$ -competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin [Online routing in triangulations. SIAM Journal on Computing, 33(4):937-951, 2004] showed that there exists an online routing algorithm that is $O(1)$ -competitive. However, a Delaunay triangulation can have $Ω(n)$ vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set $V$ of $n$ points in the Euclidean plane, of a planar geometric graph on $V$ that has small weight (within a constant factor of the weight of a minimum spanning tree on $V$ ), constant degree, and that admits a local routing strategy that is $O(1)$ -competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an $O(1)$ -competitive routing strategy.

preprint2020arXiv

Approximating the packedness of polygonal curves

In 2012 Driemel et al. \cite{DBLP:journals/dcg/DriemelHW12} introduced the concept of $c$ -packed curves as a realistic input model. In the case when $c$ is a constant they gave a near linear time $(1+\varepsilon)$ -approximation algorithm for computing the Fréchet distance between two $c$ -packed polygonal curves. Since then a number of papers have used the model. In this paper we consider the problem of computing the smallest $c$ for which a given polygonal curve in $\mathbb{R}^d$ is $c$ -packed. We present two approximation algorithms. The first algorithm is a $2$ -approximation algorithm and runs in $O(dn^2 \log n)$ time. In the case $d=2$ we develop a faster algorithm that returns a $(6+\varepsilon)$ -approximation and runs in $O((n/\varepsilon^3)^{4/3} polylog (n/\varepsilon)))$ time. We also implemented the first algorithm and computed the approximate packedness-value for 16 sets of real-world trajectories. The experiments indicate that the notion of $c$ -packedness is a useful realistic input model for many curves and trajectories.

preprint2020arXiv

On beta-Plurality Points in Spatial Voting Games

Let $V$ be a set of $n$ points in $\mathbb{R}^d$ , called voters. A point $p\in \mathbb{R}^d$ is a plurality point for $V$ when the following holds: for every $q\in\mathbb{R}^d$ the number of voters closer to $p$ than to $q$ is at least the number of voters closer to $q$ than to $p$ . Thus, in a vote where each $v\in V$ votes for the nearest proposal (and voters for which the proposals are at equal distance abstain), proposal $p$ will not lose against any alternative proposal $q$ . For most voter sets a plurality point does not exist. We therefore introduce the concept of $β$ -plurality points, which are defined similarly to regular plurality points except that the distance of each voter to $p$ (but not to $q$ ) is scaled by a factor $β$ , for some constant $0<β\leq 1$ . We investigate the existence and computation of $β$ -plurality points, and obtain the following. * Define $β^*_d := \sup \{ β: \text{any finite multiset $V $in$ \mathbb{R}^d $admits a$ β$-plurality point} \}$. We prove that $β^*_2 = \sqrt{3}/2$ , and that $1/\sqrt{d} \leq β^*_d \leq \sqrt{3}/2$ for all $d\geq 3$ . * Define $β(p, V) := \sup \{ β: \text{$p $is a$ β $-plurality point for$ V$}\}$. Given a voter set $V \in \mathbb{R}^2$ , we provide an algorithm that runs in $O(n \log n)$ time and computes a point $p$ such that $β(p, V) \geq β^*_2$ . Moreover, for $d\geq 2$ we can compute a point $p$ with $β(p,V) \geq 1/\sqrt{d}$ in $O(n)$ time. * Define $β(V) := \sup \{ β: \text{$V $admits a$ β$-plurality point}\}$. We present an algorithm that, given a voter set $V$ in $\mathbb{R}^d$ , computes an $(1-\varepsilon)\cdot β(V)$ plurality point in time $O(\frac{n^2}{\varepsilon^{3d-2}} \cdot \log \frac{n}{\varepsilon^{d-1}} \cdot \log^2 \frac {1}{\varepsilon})$ .

preprint2016arXiv

Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees

We consider the problem of augmenting an n-vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present exact algorithms for the cases when (i) the input graph is a path, running in O(n \log^3 n) time, and (ii) the input graph is a tree, running in O(n^2 \log n) time. We also present an algorithm that computes a (1+\eps)-approximation in O(n + 1/\eps^3) time, for paths in R^d, where d is a constant.

preprint2015arXiv

Finding Pairwise Intersections Inside a Query Range

We study the following problem: preprocess a set O of objects into a data structure that allows us to efficiently report all pairs of objects from O that intersect inside an axis-aligned query range Q. We present data structures of size $O(n({\rm polylog} n))$ and with query time $O((k+1)({\rm polylog} n))$ time, where k is the number of reported pairs, for two classes of objects in the plane: axis-aligned rectangles and objects with small union complexity. For the 3-dimensional case where the objects and the query range are axis-aligned boxes in R^3, we present a data structures of size $O(n\sqrt{n}({\rm polylog} n))$ and query time $O((\sqrt{n}+k)({\rm polylog} n))$ . When the objects and query are fat, we obtain $O((k+1)({\rm polylog} n))$ query time using $O(n({\rm polylog} n))$ storage.

preprint2014arXiv

Computational Aspects of Multi-Winner Approval Voting

We study computational aspects of three prominent voting rules that use approval ballots to elect multiple winners. These rules are satisfaction approval voting, proportional approval voting, and reweighted approval voting. We first show that computing the winner for proportional approval voting is NP-hard, closing a long standing open problem. As none of the rules are strategyproof, even for dichotomous preferences, we study various strategic aspects of the rules. In particular, we examine the computational complexity of computing a best response for both a single agent and a group of agents. In many settings, we show that it is NP-hard for an agent or agents to compute how best to vote given a fixed set of approval ballots from the other agents.

preprint2014arXiv

Increasing-Chord Graphs On Point Sets

We tackle the problem of constructing increasing-chord graphs spanning point sets. We prove that, for every point set P with n points, there exists an increasing-chord planar graph with O(n) Steiner points spanning P. Further, we prove that, for every convex point set P with n points, there exists an increasing-chord graph with O(n log n) edges (and with no Steiner points) spanning P.

preprint2013arXiv

Augmenting graphs to minimize the diameter

We study the problem of augmenting a weighted graph by inserting edges of bounded total cost while minimizing the diameter of the augmented graph. Our main result is an FPT 4-approximation algorithm for the problem.

preprint2013arXiv

SEFE with No Mapping via Large Induced Outerplane Graphs in Plane Graphs

We show that every $n$ -vertex planar graph admits a simultaneous embedding with no mapping and with fixed edges with any $(n/2)$ -vertex planar graph. In order to achieve this result, we prove that every $n$ -vertex plane graph has an induced outerplane subgraph containing at least $n/2$ vertices. Also, we show that every $n$ -vertex planar graph and every $n$ -vertex planar partial 3-tree admit a simultaneous embedding with no mapping and with fixed edges.

preprint2012arXiv

A Generalization of the Convex Kakeya Problem

Given a set of line segments in the plane, not necessarily finite, what is a convex region of smallest area that contains a translate of each input segment? This question can be seen as a generalization of Kakeya's problem of finding a convex region of smallest area such that a needle can be rotated through 360 degrees within this region. We show that there is always an optimal region that is a triangle, and we give an optimal Θ(n log n)-time algorithm to compute such a triangle for a given set of n segments. We also show that, if the goal is to minimize the perimeter of the region instead of its area, then placing the segments with their midpoint at the origin and taking their convex hull results in an optimal solution. Finally, we show that for any compact convex figure G, the smallest enclosing disk of G is a smallest-perimeter region containing a translate of every rotated copy of G.

preprint2011arXiv

Quickest Path Queries on Transportation Network

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. We give an exact algorithm for the basic version of the problem: given a transportation network of total complexity n in the Euclidean plane, a source point s and a destination point t, and the quickest path between s and t. We also show how the transportation network can be preprocessed in time O(n^2 log n) into a data structure of size O(n^2) such that (1 + ε)-approximate cheapest path cost queries between any two points in the plane can be answered in time O(1ε^4 log n).

preprint2010arXiv

Farthest-Polygon Voronoi Diagrams

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.

preprint2010arXiv

Notes on large angle crossing graphs

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.

preprint2010arXiv

Planar Visibility: Testing and Counting

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$ . We present several data structures for the two query problems. The structures build upon a result by O'Rourke and Suri (1984) who showed that the subset, $V_S(s)$ , of $\R^2$ that is weakly visible from a segment $s$ can be represented as the union of a set, $C_S(s)$ , of $O(n^2)$ triangles, even though the complexity of $V_S(s)$ can be $Ω(n^4)$ . We define a variant of their covering, give efficient output-sensitive algorithms for computing it, and prove additional properties needed to obtain approximation bounds. Some of our bounds rely on a new combinatorial result that relates the number of segments of $S$ visible from a point $p$ to the number of triangles in $\bigcup_{s\in S} C_S(s)$ that contain $p$ .

preprint2007arXiv

Aperture-Angle and Hausdorff-Approximation of Convex Figures

The aperture angle alpha(x, Q) of a point x not in Q in the plane with respect to a convex polygon Q is the angle of the smallest cone with apex x that contains Q. The aperture angle approximation error of a compact convex set C in the plane with respect to an inscribed convex polygon Q of C is the minimum aperture angle of any x in C Q with respect to Q. We show that for any compact convex set C in the plane and any k > 2, there is an inscribed convex k-gon Q of C with aperture angle approximation error (1 - 2/(k+1)) pi. This bound is optimal, and settles a conjecture by Fekete from the early 1990s. The same proof technique can be used to prove a conjecture by Brass: If a polygon P admits no approximation by a sub-k-gon (the convex hull of k vertices of P) with Hausdorff distance sigma, but all subpolygons of P (the convex hull of some vertices of P) admit such an approximation, then P is a (k+1)-gon. This implies the following result: For any k > 2 and any convex polygon P of perimeter at most 1 there is a sub-k-gon Q of P such that the Hausdorff-distance of P and Q is at most 1/(k+1) * sin(pi/(k+1)).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Joachim Gudmundsson

Research overview

Is this your work?

17 publications

Covering a set of line segments with a few squares

Exploring Sub-skeleton Trajectories for Interpretable Recognition of Sign Language

Local Routing in Sparse and Lightweight Geometric Graphs

Approximating the packedness of polygonal curves

On beta-Plurality Points in Spatial Voting Games

Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees

Finding Pairwise Intersections Inside a Query Range

Computational Aspects of Multi-Winner Approval Voting

Increasing-Chord Graphs On Point Sets

Augmenting graphs to minimize the diameter

SEFE with No Mapping via Large Induced Outerplane Graphs in Plane Graphs

A Generalization of the Convex Kakeya Problem

Quickest Path Queries on Transportation Network

Farthest-Polygon Voronoi Diagrams

Notes on large angle crossing graphs

Planar Visibility: Testing and Counting

Aperture-Angle and Hausdorff-Approximation of Convex Figures

See the researcher in context

Building this map preview