Soccer is a rich testbed for studying multi-agent adversarial systems. In this work we focus on the task of reconstructing the noisy trajectories of soccer agents (players and the ball). Previous works that model the behaviours of agents in soccer are limited in two respects: (i) they only focus on short-term context windows (less than or equal to 10 seconds) which are not suitable for reconstructing trajectories impacted by long-term noise, and (ii) they exclusively rely on trajectory context, and do not leverage soccer's auxiliary data streams that can provide additional context. Our Event2Tracking model addresses these limitations. First, our architecture models soccer's long-term structure by processing long-term trajectories (60 seconds in duration). Secondly, our architecture is multimodal. Specifically, it fuses soccer tracking data with event data (which specifies the high-level semantic events that transpire in a game), providing rich context that cannot strictly be inferred from the raw trajectories. We evaluate our method empirically using a reconstruction loss metric. Compared to state-of-the-art approaches, our method substantially improves the accuracy of the ball's and players' reconstructed trajectories.

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.

Let V be a set of n points in mathcal R d , called voters . A point p ∈ mathcal R d is a plurality point for V when the following holds: For every q ∈ mathcal 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 ∈ 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< β ⩽ 1. We investigate the existence and computation of β -plurality points and obtain the following results. • Define β * d := {β : any finite multiset V in mathcal R d admits a β-plurality point. We prove that β * d = √3/2, and that 1/√ d ⩽ β * d ⩽ √ 3/2 for all d ⩾ 3. • Define β ( p, V ) := sup {β : p is a β -plurality point for V }. Given a voter set V in mathcal R 2 , we provide an algorithm that runs in O ( n log n ) time and computes a point p such that β ( p , V ) ⩾ β * b . Moreover, for d ⩾ 2, we can compute a point p with β ( p , V ) ⩾ 1/√ d in O ( n ) time. • Define β ( V ) := sup { β : V admits a β -plurality point}. We present an algorithm that, given a voter set V in mathcal R d , computes an ((1-ɛ)ċ β ( V ))-plurality point in time O n 2 ɛ 3d-2 ċ log n ɛ d-1 ċ log 2 1ɛ).

Let V be a set of n points in ℝ^d, called voters. A point p ∈ ℝ^d is a plurality point for V when the following holds: for every q ∈ ℝ^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 ∈ 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<β⩽1. We investigate the existence and computation of β-plurality points, and obtain the following results. - Define β^*_d := sup{β : any finite multiset V in ℝ^d admits a β-plurality point}. We prove that β^*₂ = √3/2, and that 1/√d ⩽ β^*_d ⩽ √3/2 for all d⩾3. - Define β(V) := sup {β : V admits a β-plurality point}. We present an algorithm that, given a voter set V in {ℝ}^d, computes an (1-ε)⋅ β(V) plurality point in time O(n²/ε^(3d-2) ⋅ log(n/ε^(d-1)) ⋅ log²(1/ε)).

The Euclidean k-Center problem is a classical problem that has been extensively studied in computer science. Given a set G of n points in Euclidean space, the problem is to determine a set C of k centers (not necessarily part of G) such that the maximum distance between a point in G and its nearest neighbor in C is minimized. In this paper we study the corresponding (k, ℓ)-CENTER problem for polygonal curves under the Fréchet distance, that is, given a set G of n polygonal curves in ℝd, each of complexity m, determine a set C of k polygonal curves in ℝd, each of complexity ℓ, such that the maximum Fréchet distance of a curve in G to its closest curve in C is minimized. In their 2016 paper, Driemel, Krivošija, and Sohler give a near-linear time (1 + ε-approximation algorithm for one-dimensional curves, assuming that k and ℓ are constants. In this paper, we substantially extend and improve the known approximation bounds for curves in dimension 2 and higher. Our analysis thus extends to application-relevant input data such as GPS-trajectories and protein backbones. We show that, if ℓ is part of the input, then there is no polynomial-time approximation scheme unless P = NP. Our constructions yield different bounds for one and two-dimensional curves and the discrete and continuous Fréchet distance. In the case of the discrete Fréchet distance on two-dimensional curves, we show hardness of approximation within a factor close to 2.598. This result also holds when k = 1, and the NP-hardness extends to the case that ℓ = ∞, i.e., for the problem of computing the minimum-enclosing ball under the Fréchet distance. Finally, we observe that a careful adaptation of Gonzalez’ algorithm in combination with a curve simplification yields a 3-approximation in any dimension, provided that an optimal simplification can be computed exactly. We conclude that our approximation bounds are close to being tight.