Joachim Gudmundsson

Sarita de Berg, Joachim Gudmundsson, Peter Kramer et al.

We investigate multiple fundamental variants of the classic coordinated motion planning (CMP) problem for unit square robots in the plane under the $L_1$ metric. In coordinated motion planning, we are given two arrangements of $k$ robots and are tasked with finding a movement schedule that minimizes a certain objective function. The two most prominent objective functions are the sum of distances traveled (Min-Sum) and the latest time of arrival (Min-Makespan). Both objectives have previously been studied extensively. We introduce a new objective function for CMP in the plane. The proposed Min-Exposure objective function defines a set of polygonal regions in the plane that provide cover and asks for a schedule with minimal elapsed time during which at least one robot is partially or fully outside of these regions. We give an $\mathcal{O}(n^4\log n)$ time algorithm that computes exposure-minimal schedules for $k=2$ robots, and an XP algorithm for arbitrary $k$. As a result of independent interest, we leverage new insights to prove that both the Min-Makespan and Min-Sum objectives are fixed-parameter tractable (FPT) parameterized by the number of robots. Our parameterized complexity results generalize known FPT results for rectangular grid graphs [Eiben, Ganian, and Kanj, SoCG'23].

Joachim Gudmundsson, Yuan Sha, Sampson Wong

In the celebrated paper of Henzinger, Klein, Rao and Subramanian (1997), it was shown that planar graphs admit a linear time single-source shortest path algorithm. Their algorithm unfortunately does not extend to Euclidean graph classes. We give criteria and prove that any Euclidean graph class satisfying the criteria admits a linear time single-source shortest path algorithm. As a main ingredient, we show that the contracted graphs of these Euclidean graph classes admit sublinear separators.

Lintao Wang, Shiwen Xu, Michael Horton et al.

Predicting soccer match outcomes is a challenging task due to the inherently unpredictable nature of the game and the numerous dynamic factors influencing results. While it conventionally relies on meticulous feature engineering, deep learning techniques have recently shown a great promise in learning effective player and team representations directly for soccer outcome prediction. However, existing methods often overlook the heterogeneous nature of interactions among players and teams, which is crucial for accurately modeling match dynamics. To address this gap, we propose HIGFormer (Heterogeneous Interaction Graph Transformer), a novel graph-augmented transformer-based deep learning model for soccer outcome prediction. HIGFormer introduces a multi-level interaction framework that captures both fine-grained player dynamics and high-level team interactions. Specifically, it comprises (1) a Player Interaction Network, which encodes player performance through heterogeneous interaction graphs, combining local graph convolutions with a global graph-augmented transformer; (2) a Team Interaction Network, which constructs interaction graphs from a team-to-team perspective to model historical match relationships; and (3) a Match Comparison Transformer, which jointly analyzes both team and player-level information to predict match outcomes. Extensive experiments on the WyScout Open Access Dataset, a large-scale real-world soccer dataset, demonstrate that HIGFormer significantly outperforms existing methods in prediction accuracy. Furthermore, we provide valuable insights into leveraging our model for player performance evaluation, offering a new perspective on talent scouting and team strategy analysis.

Joachim Gudmundsson, Martin P. Seybold, John Pfeifer

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.

Joachim Gudmundsson, Michael Horton, John Pfeifer et al.

We present a scalable approach for range and $k$ nearest neighbor queries under computationally expensive metrics, like the continuous Fréchet distance on trajectory data. Based on clustering for metric indexes, we obtain a dynamic tree structure whose size is linear in the number of trajectories, regardless of the trajectory's individual sizes or the spatial dimension, which allows one to exploit low `intrinsic dimensionality' of data sets for effective search space pruning. Since the distance computation is expensive, generic metric indexing methods are rendered impractical. We present strategies that (i) improve on known upper and lower bound computations, (ii) build cluster trees without any or very few distance calls, and (iii) search using bounds for metric pruning, interval orderings for reduction, and randomized pivoting for reporting the final results. We analyze the efficiency and effectiveness of our methods with extensive experiments on diverse synthetic and real-world data sets. The results show improvement over state-of-the-art methods for exact queries, and even further speed-ups are achieved for queries that may return approximate results. Surprisingly, the majority of exact nearest-neighbor queries on real data sets are answered without any distance computations.

Younjin Chung, Joachim Gudmundsson, Masahiro Takatsuka

Estimating output changes by input changes is the main task in causal analysis. In previous work, input and output Self-Organizing Maps (SOMs) were associated for causal analysis of multivariate and nonlinear data. Based on the association, a weight distribution of the output conditional on a given input was obtained over the output map space. Such a weighted SOM pattern of the output changes when the input changes. In order to analyze the change, it is important to measure the difference of the patterns. Many methods have been proposed for the dissimilarity measure of patterns. However, it remains a major challenge when attempting to measure how the patterns change. In this paper, we propose a visualization approach that simplifies the comparison of the difference in terms of the pattern property. Using this approach, the change can be analyzed by integrating colors and star glyph shapes representing the property dissimilarity. Ecological data is used to demonstrate the usefulness of our approach and the experimental results show that our approach provides the change information effectively.

Haris Aziz, Serge Gaspers, Joachim Gudmundsson et al.

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.