Zobrazeno 1 - 10
of 91
pro vyhledávání: '"Roeloffzen, Marcel"'
Autor:
van Beusekom, Nathan, van Kreveld, Marc, van Mulken, Max, Roeloffzen, Marcel, Speckmann, Bettina, Wulms, Jules
Detecting location-correlated groups in point sets is an important task in a wide variety of applications areas. In addition to merely detecting such groups, the group's shape carries meaning as well. In this paper, we represent a group's shape using
Externí odkaz:
http://arxiv.org/abs/2402.12285
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
Autor:
Abel, Zachary, Akitaya, Hugo, Chiu, Man-Kwun, Demaine, Erik D., Demaine, Martin L., Hesterberg, Adam, Korman, Matias, Lynch, Jayson, van Renssen, André, Roeloffzen, Marcel
We study Snipperclips, a computer puzzle game whose objective is to create a target shape with two tools. The tools start as constant-complexity shapes, and each tool can snip (i.e., subtract its current shape from) the other tool. We study the compu
Externí odkaz:
http://arxiv.org/abs/2105.08305
We study the problem of polygonal curve simplification under uncertainty, where instead of a sequence of exact points, each uncertain point is represented by a region, which contains the (unknown) true location of the vertex. The regions we consider
Externí odkaz:
http://arxiv.org/abs/2103.09223
Autor:
Buchin, Kevin, Fan, Chenglin, Löffler, Maarten, Popov, Aleksandr, Raichel, Benjamin, Roeloffzen, Marcel
Publikováno v:
ACM Transactions on Algorithms 19.3 (2023), article no. 29
In this paper we study a wide range of variants for computing the (discrete and continuous) Fr\'echet distance between uncertain curves. We define an uncertain curve as a sequence of uncertainty regions, where each region is a disk, a line segment, o
Externí odkaz:
http://arxiv.org/abs/2004.11862
We study the geodesic Voronoi diagram of a set $S$ of $n$ linearly moving sites inside a static simple polygon $P$ with $m$ vertices. We identify all events where the structure of the Voronoi diagram changes, bound the number of such events, and then
Externí odkaz:
http://arxiv.org/abs/2002.05910
Autor:
Chiu, Man-Kwun, Cleve, Jonas, Klost, Katharina, Korman, Matias, Mulzer, Wolfgang, van Renssen, André, Roeloffzen, Marcel, Willert, Max
Let $P$ be an $x$-monotone orthogonal polygon with $n$ vertices. We call $P$ a simple histogram if its upper boundary is a single edge; and a double histogram if it has a horizontal chord from the left boundary to the right boundary. Two points $p$ a
Externí odkaz:
http://arxiv.org/abs/1902.06599
Autor:
Arseneva, Elena, Chiu, Man-Kwun, Korman, Matias, Markovic, Aleksandar, Okamoto, Yoshio, Ooms, Aurélien, van Renssen, André, Roeloffzen, Marcel
We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of $n$ vertices and $h$ holes. We introduce a \emph{graph of oriented distances} to encode the distance between pairs of poi
Externí odkaz:
http://arxiv.org/abs/1712.05538
Autor:
Carmi, Paz, Chiu, Man Kwun, Katz, Matthew J., Korman, Matias, Okamoto, Yoshio, van Renssen, André, Roeloffzen, Marcel, Shiitada, Taichi, Smorodinsky, Shakhar
We prove a geometric version of the graph separator theorem for the unit disk intersection graph: for any set of $n$ unit disks in the plane there exists a line $\ell$ such that $\ell$ intersects at most $O(\sqrt{(m+n)\log{n}})$ disks and each of the
Externí odkaz:
http://arxiv.org/abs/1709.02579
Autor:
Barba, Luis, Cardinal, Jean, Korman, Matias, Langerman, Stefan, van Renssen, André, Roeloffzen, Marcel, Verdonschot, Sander
In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a graph under insertion and deletion of vertices and edges. We present two algorithms that achieve different trade-of
Externí odkaz:
http://arxiv.org/abs/1708.09080