Zobrazeno 1 - 10
of 300
pro vyhledávání: '"Buchin, Kevin"'
Map matching is a common task when analysing GPS tracks, such as vehicle trajectories. The goal is to match a recorded noisy polygonal curve to a path on the map, usually represented as a geometric graph. The Fr\'echet distance is a commonly used met
Externí odkaz:
http://arxiv.org/abs/2407.19304
Spanner constructions focus on the initial design of the network. However, networks tend to improve over time. In this paper, we focus on the improvement step. Given a graph and a budget $k$, which $k$ edges do we add to the graph to minimise its dil
Externí odkaz:
http://arxiv.org/abs/2407.04614
We study the problem of multi-agent online graph exploration, in which a team of k agents has to explore a given graph, starting and ending on the same node. The graph is initially unknown. Whenever a node is visited by an agent, its neighborhood and
Externí odkaz:
http://arxiv.org/abs/2402.13845
Autor:
Buchin, Kevin, Gudmundsson, Joachim, Kalb, Antonia, Popov, Aleksandr, Rehs, Carolin, van Renssen, André, Wong, Sampson
Given a point set $P$ in the Euclidean plane and a parameter $t$, we define an \emph{oriented $t$-spanner} $G$ as an oriented subgraph of the complete bi-directed graph such that for every pair of points, the shortest closed walk in $G$ through those
Externí odkaz:
http://arxiv.org/abs/2306.17097
Autor:
Buchin, Kevin, Evans, Will, Frati, Fabrizio, Kostitsyna, Irina, Löffler, Maarten, Ophelders, Tim, Wolff, Alexander
In this paper, we investigate crossing-free 3D morphs between planar straight-line drawings. We show that, for any two (not necessarily topologically equivalent) planar straight-line drawings of an $n$-vertex planar graph, there exists a piecewise-li
Externí odkaz:
http://arxiv.org/abs/2210.05384
Autor:
Banyassady, Bahareh, de Berg, Mark, Bringmann, Karl, Buchin, Kevin, Fernau, Henning, Halperin, Dan, Kostitsyna, Irina, Okamoto, Yoshio, Slot, Stijn
We consider the unlabeled motion-planning problem of $m$ unit-disc robots moving in a simple polygonal workspace of $n$ edges. The goal is to find a motion plan that moves the robots to a given set of $m$ target positions. For the unlabeled variant,
Externí odkaz:
http://arxiv.org/abs/2205.07777
Autor:
Afshani, Peyman, de Berg, Mark, Buchin, Kevin, Gao, Jie, Loffler, Maarten, Nayyeri, Amir, Raichel, Benjamin, Sarkar, Rik, Wang, Haotian, Yang, Hao-Tsung
We consider the following surveillance problem: Given a set $P$ of $n$ sites in a metric space and a set of $k$ robots with the same maximum speed, compute a patrol schedule of minimum latency for the robots. Here a patrol schedule specifies for each
Externí odkaz:
http://arxiv.org/abs/2203.07280
Autor:
Buchin, Kevin, Flocchini, Paola, Kostitsyna, Irina, Peters, Tom, Santoro, Nicola, Wada, Koichi
We consider distributed systems of identical autonomous computational entities, called robots, moving and operating in the plane in synchronous Look-Compute-Move (LCM) cycles. The algorithmic capabilities of these systems have been extensively invest
Externí odkaz:
http://arxiv.org/abs/2203.06546
Dynamic Time Warping is arguably the most popular similarity measure for time series, where we define a time series to be a one-dimensional polygonal curve. The drawback of Dynamic Time Warping is that it is sensitive to the sampling rate of the time
Externí odkaz:
http://arxiv.org/abs/2203.04531
Autor:
Buchin, Kevin, Custers, Bram, van der Hoog, Ivor, Löffler, Maarten, Popov, Aleksandr, Roeloffzen, Marcel, Staals, Frank
Let $P$ be a simple polygon with $n$ vertices, and let $A$ be a set of $m$ points or line segments inside $P$. We develop data structures that can efficiently count the number of objects from $A$ that are visible to a query point or a query segment.
Externí odkaz:
http://arxiv.org/abs/2201.03490