Currently Under Review
-
The tight spanning ratio of the rectangle Delaunay triangulation
, , , and .Abstract: Spanner construction is a well-studied problem and Delaunay triangulations are among the most popular spanners. Tight bounds are known if the Delaunay triangulation is constructed using an equilateral triangle, a square, or a regular hexagon. However, all other shapes have remained elusive. In this paper we extend the restricted class of spanners for which tight bounds are known. We prove that Delaunay triangulations constructed using rectangles with aspect ratio $A$ have spanning ratio at most $\sqrt{2} \sqrt{1+A^2 + A \sqrt{A^2 + 1}}$, which matches the known lower bound.
Submitted to Algorithmica.
@article{RSSW2023RectangleDelaunayTightJournal, author={van Renssen, Andr\'e and Sha, Yuan and Sun, Yucheng and Wong, Sampson}, title={The Tight Spanning Ratio of the Rectangle {D}elaunay Triangulation}, year={2023}, journal={ArXiv e-prints}, archivePrefix={arXiv}, eprint={2211.11987}, note={\href{http://arxiv.org/abs/2211.11987}{arXiv:2211.11987}}, url={http://arxiv.org/abs/2211.11987} } -
Shortest paths of mutually visible robots
, , and .Abstract: Given a set of $n$ point robots inside a simple polygon $P$, the task is to move the robots from their starting positions to their target positions along their shortest paths, while the mutual visibility of these robots is preserved. Previous work only considered two robots. In this paper, we present an $O(mn)$ time algorithm, where $m$ is the complexity of the polygon, when all the starting positions lie on a line segment $S$, all the target positions lie on a line segment $T$, and $S$ and $T$ do not intersect. We also argue that there is no polynomial-time algorithm, whose running time depends only on $n$ and $m$, that uses a single strategy for the case where $S$ and $T$ intersect.
Submitted to International Journal of Computational Geometry & Applications (IJCGA).
@article{AGR2023ShortestPathsJournal, author={Alsaedi, Rusul J. and Gudmundsson, Joachim and van Renssen, Andr\'e}, title={Shortest Paths of Mutually Visible Robots}, year={2023}, journal={ArXiv e-prints}, archivePrefix={arXiv}, eprint={2309.16901}, note={\href{http://arxiv.org/abs/2309.16901}{arXiv:2309.16901}}, url={http://arxiv.org/abs/2309.16901} } -
The mutual visibility problem for fat robots
, , and .Abstract: Given a set of $n\geq 1$ unit disk robots in the Euclidean plane, we consider the fundamental problem of providing mutual visibility to them: the robots must reposition themselves to reach a configuration where they all see each other. This problem arises under obstructed visibility, where a robot cannot see another robot if there is a third robot on the straight line segment between them. This problem was solved by Sharma et al. [G. Sharma, R. Alsaedi, C. Busch, and S. Mukhopadhyay. The complete visibility problem for fat robots with lights. In Proceedings of the 19th International Conference on Distributed Computing and Networking, pages 1-4, 2018.] in the luminous robots model, where each robot is equipped with an externally visible light that can assume colors from a fixed set of colors, using 9 colors and $O(n)$ rounds. In this work, we present an algorithm that requires only 2 colors and $O(n)$ rounds. The number of colors is optimal since at least two colors are required for point robots [G.A. Di Luna, P. Flocchini, S.G. Chaudhuri, F. Poloni, N. Santoro, and G. Viglietta. Mutual visibility by luminous robots without collisions. Information and Computation, 254:392-418, 2017.].
Submitted to Computational Geometry: Theory and Applications (CGTA).
@article{AGR2023RobotsJournal, author={Alsaedi, Rusul J. and Gudmundsson, Joachim and van Renssen, Andr\'e}, title={The Mutual Visibility Problem for Fat Robots}, year={2023}, journal={ArXiv e-prints}, archivePrefix={arXiv}, eprint={2206.14423}, note={\href{http://arxiv.org/abs/2206.14423}{arXiv:2206.14423}}, url={http://arxiv.org/abs/2206.14423} }
Journal Papers
-
Generalized sweeping line spanners
and .Abstract: We present sweeping line graphs, a generalization of $\Theta$-graphs. We show that these graphs are spanners of the complete graph, as well as of the visibility graph when line segment constraints or polygonal obstacles are considered. Our proofs use general inductive arguments to make the step to the constrained setting. These same arguments could apply to other spanner constructions in the unconstrained setting, removing the need to find separate proofs that they are spanning in the constrained and polygonal obstacle settings.
Theoretical Computer Science (TCS) special issue of COCOON 2022, 989:114390, 2024.
@article{LR2024SweepingJournal, author={Lee, Keenan and van Renssen, Andr\'e}, title={Generalized Sweeping Line Spanners}, journal={Theoretical Computer Science (TCS) special issue of COCOON 2022}, year={2024}, volume={989}, pages={114390}, doi={10.1016/j.tcs.2024.114390} } -
Kinetic geodesic Voronoi diagrams in a simple polygon
, , , and .Abstract: 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 develop a kinetic data structure (KDS) that maintains the geodesic Voronoi diagram as the sites move. To this end, we first analyze how often a single bisector, defined by two sites, or a single Voronoi center, defined by three sites, can change. For both these structures we prove that the number of such changes is at most $O(m^3)$, and that this is tight in the worst case. Moreover, we develop compact, responsive, local, and efficient kinetic data structures for both structures. Our data structures use linear space and process a worst-case optimal number of events. Our bisector and Voronoi center kinetic data structures handle each event in $O(\log^2 m)$ time. Both structures can be extended to efficiently support updating the movement of the sites as well. Using these data structures as building blocks we obtain a compact KDS for maintaining the full geodesic Voronoi diagram.
SIAM Journal on Discrete Mathematics (SIDMA), 37(4):2276–2311, 2023.
@article{KRRS2023KineticJournal, author={Korman, Matias and van Renssen, Andr\'e and Roeloffzen, Marcel and Staals, Frank}, title={Kinetic Geodesic {V}oronoi Diagrams in a Simple Polygon}, journal={SIAM Journal on Discrete Mathematics (SIDMA)}, year={2023}, volume={37}, number={4}, pages={2276-2311}, doi={10.1137/20M1384804} } -
Graphs with large total angular resolution
, , , , , , and .Abstract: The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawing: the angular resolution, which is the minimum angle between incident edges, and the crossing resolution, which is the minimum angle between crossing edges. We consider the total angular resolution of a graph, which is the maximum total angular resolution of a straight-line drawing of this graph.We prove tight bounds for the number of edges for graphs for some values of the total angular resolution up to a finite number of well specified exceptions of constant size. In addition, we show that deciding whether a graph has total angular resolution at least $60^{\circ}$ is NP-hard. Further we present some special graphs and their total angular resolution.
Theoretical Computer Science (TCS), 943:73–88, 2023.
@article{AKOPPRV2023AngularResolutionJournal, author={Aichholzer, Oswin and Korman, Matias and Okamoto, Yoshio and Parada, Irene and Perz, Daniel and van Renssen, Andr\'e and Vogtenhuber, Birgit}, title={Graphs with large total angular resolution}, journal={Theoretical Computer Science (TCS)}, year={2023}, volume={943}, pages={73-88}, doi={10.1016/j.tcs.2022.12.010} } -
Local routing in a tree metric 1-spanner
, , and .Abstract: Solomon and Elkin [13] constructed a shortcutting scheme for weighted trees which results in a 1-spanner for the tree metric induced by the input tree. The spanner has logarithmic lightness, logarithmic diameter, a linear number of edges and bounded degree (provided the input tree has bounded degree). This spanner has been applied in a series of papers devoted to designing bounded degree, low-diameter, low-weight $(1+\epsilon)$-spanners in Euclidean and doubling metrics. In this paper, we present a simple local routing algorithm for this tree metric spanner. The algorithm has a routing ratio of 1, is guaranteed to terminate after $O(\log n)$ hops and requires $O(\Delta \log n)$ bits of storage per vertex where $\Delta$ is the maximum degree of the tree on which the spanner is constructed. This local routing algorithm can be adapted to a local routing algorithm for a doubling metric spanner which makes use of the shortcutting scheme.
Journal of Combinatorial Optimization (JOCO) special issue of COCOON 2020, 44:2642–2660, 2022.
@article{BGR2022TreeRoutingJournal, author={Brankovic, Milutin and Gudmundsson, Joachim and van Renssen, Andr\'e}, title={Local Routing in a Tree Metric 1-Spanner}, journal={Journal of Combinatorial Optimization (JOCO) special issue of COCOON 2020}, year={2022}, volume={44}, pages={2642-2660}, doi={10.1007/s10878-021-00784-4} } -
Covering a set of line segments with a few squares
, , , , , and .Abstract: 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 $k=4$ unit-sized, axis-parallel squares. We give linear time algorithms for $k\leq 3$ and an $O(n \log n)$ time algorithm for $k=4$.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. For $k=2$ and $k=3$ we construct data structures of size $O(n\alpha(n)\log n)$ in $O(n\alpha(n) \log n)$ time, so that we can test if an arbitrary subtrajectory can be $k$-covered in $O(\log n)$ time.
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. We give $O(n2^{\alpha(n)}\log^2 n)$ time algorithms for $k\leq 2$.
Theoretical Computer Science (TCS) special issue of CIAC 2021, 923:74–98, 2022.
@article{GKRSWW2022TrajectoryCoveringJournal, author={Gudmundsson, Joachim and van de Kerkhof, Mees and van Renssen, Andr\'e and Staals, Frank and Wiratma, Lionov and Wong, Sampson}, title={Covering a set of line segments with a few squares}, journal={Theoretical Computer Science (TCS) special issue of CIAC 2021}, year={2022}, volume={923}, pages={74-98}, doi={10.1016/j.tcs.2022.04.053} } -
Local routing in sparse and lightweight geometric graphs
, , , , and .Abstract: 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 [P. Bose and P. 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 $\Omega(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.
Algorithmica, 84(5):1316–1340, 2022.
@article{AGLNR2022LightRoutingJournal, author={Ashvinkumar, Vikrant and Gudmundsson, Joachim and Levcopoulos, Christos and Nilsson, Bengt J. and van Renssen, Andr\'e}, title={Local Routing in Sparse and Lightweight Geometric Graphs}, journal={Algorithmica}, year={2022}, volume={84}, number={5}, pages={1316–1340}, doi={10.1007/s00453-022-00930-2} } -
Translation invariant Fréchet distance queries
, , , and .Abstract: The Fréchet distance is a popular similarity measure between curves. For some applications, it is desirable to match the curves under translation before computing the Fréchet distance between them. This variant is called the Translation Invariant Fréchet distance, and algorithms to compute it are well studied. The query version, however, is much less well understood.We study Translation Invariant Fréchet distance queries in a restricted setting of horizontal query segments. More specifically, we prepocess a trajectory in $O(n^2 \log^2 n) $ time and space, such that for any subtrajectory and any horizontal query segment we can compute their Translation Invariant Fréchet distance in $O(\text{polylog } n)$ time. We hope this will be a step towards answering Translation Invariant Fréchet queries between arbitrary trajectories.
Algorithmica, 83(11):3514–3533, 2021.
@article{GRSW2021Frechet, author={Gudmundsson, Joachim and van Renssen, Andr\'e and Saeidi, Zeinab and Wong, Sampson}, title={Translation Invariant {F}r\'echet Distance Queries}, journal={Algorithmica}, year={2021}, volume={83}, number={11}, pages={3514-3533}, doi={10.1007/s00453-021-00865-0} } -
Snipperclips: Cutting tools into desired polygons using themselves
, , , , , , , , , and .Abstract: 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 computational problem of, given a target shape represented by a polygonal domain of $n$ vertices, is it possible to create it as one of the tools’ shape via a sequence of snip operations? If so, how many snip operations are required? We consider several variants of the problem (such as allowing the tools to be disconnected and/or using an undo operation) and bound the number of operations needed for each of the variants.
Computational Geometry: Theory and Applications (CGTA), 98:101784, 2021.
@article{AACDDHKLRR2021SnipperclipsJournal, author={Abel, Zachary and Akitaya, Hugo A. and Chiu, Man-Kwun and Demaine, Erik D. and Demaine, Martin L. and Hesterberg, Adam and Korman, Matias and Lynch, Jayson and van Renssen, Andr\'e and Roeloffzen, Marcel}, title={Snipperclips: {C}utting Tools into Desired Polygons using Themselves}, journal={Computational Geometry: Theory and Applications (CGTA)}, year={2021}, volume={98}, pages={101784}, doi={10.1016/j.comgeo.2021.101784} } -
Universal reconfiguration of facet-connected modular robots by pivots: The $O(1)$ musketeers
, , , , , , , , , , and .Abstract: We present the first universal reconfiguration algorithm for transforming a modular robot between any two facet-connected square-grid configurations using pivot moves. More precisely, we show that five extra “helper” modules (“musketeers”) suffice to reconfigure the remaining $n$ modules between any two given configurations. Our algorithm uses $O(n^2)$ pivot moves, which is worst-case optimal. Previous reconfiguration algorithms either require less restrictive “sliding” moves, do not preserve facet-connectivity, or for the setting we consider, could only handle a small subset of configurations defined by a local forbidden pattern. Configurations with the forbidden pattern do have disconnected reconfiguration graphs (discrete configuration spaces), and indeed we show that they can have an exponential number of connected components. But forbidding the local pattern throughout the configuration is far from necessary, as we show that just a constant number of added modules (placed to be freely reconfigurable) suffice for universal reconfigurability. We also classify three different models of natural pivot moves that preserve facet-connectivity, and show separations between these models.
Algorithmica, 83(5):1316–1351, 2021.
@article{AADDDFKPPRS2021RobotsJournal, author={Akitaya, Hugo A. and Arkin, Esther D. and Damian, Mirela and Demaine, Erik D. and Dujmovi\'c, Vida and Flatland, Robin and Korman, Matias and Palop, Belen and Parada, Irene and van Renssen, Andr\'e and Sacrist\'an, Vera}, title={Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: {T}he {$O(1)$} Musketeers}, journal={Algorithmica}, year={2021}, volume={83}, number={5}, pages={1316–1351}, doi={10.1007/s00453-020-00784-6} } -
Constrained routing between non-visible vertices
, , , and .Abstract: In this paper we study local routing strategies on geometric graphs. Such strategies use geometric properties of the graph like the coordinates of the current and target nodes to route. Specifically, we study routing strategies in the presence of constraints which are obstacles that edges of the graph are not allowed to cross. Let $P$ be a set of $n$ points in the plane and let $S$ be a set of line segments whose endpoints are in $P$, with no two line segments intersecting properly. We present the first deterministic 1-local $O(1)$-memory routing algorithm that is guaranteed to find a path between two vertices in the visibility graph of $P$ with respect to a set of constraints $S$. The strategy never looks beyond the direct neighbors of the current node and does not store more than $O(1)$-information to reach the target.We then turn our attention to finding competitive routing strategies. We show that when routing on any triangulation $T$ of $P$ such that $S\subseteq T$, no $o(n)$-competitive routing algorithm exists when the routing strategy restricts its attention to the triangles intersected by the line segment from the source to the target (a technique commonly used in the unconstrained setting). Finally, we provide an $O(n)$-competitive deterministic 1-local $O(1)$-memory routing algorithm on any such $T$, which is optimal in the worst case, given the lower bound.
Theoretical Computer Science (TCS), 861:144–154, 2021.
@article{BKRV2021RoutingJournal, author={Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Verdonschot, Sander}, title={Constrained Routing Between Non-Visible Vertices}, journal={Theoretical Computer Science (TCS)}, year={2021}, volume={861}, pages={144-154}, doi={10.1016/j.tcs.2021.02.017} } -
Bounded-degree spanners in the presence of polygonal obstacles
and .Abstract: Let $V$ be a finite set of vertices in the plane and $S$ be a finite set of polygonal obstacles. We show how to construct a plane $2$-spanner of the visibility graph of $V$ with respect to $S$. As this graph can have unbounded degree, we modify it in three easy-to-follow steps, in order to bound the degree to $7$ at the cost of slightly increasing the spanning ratio to 6.
Theoretical Computer Science (TCS) special issue of COCOON 2020, 854:159–173, 2021.
@article{RW2021BoundedDegreePolygonalObstaclesJournal, author={van Renssen, Andr\'e and Wong, Gladys}, title={Bounded-Degree Spanners in the Presence of Polygonal Obstacles}, journal={Theoretical Computer Science (TCS) special issue of COCOON 2020}, year={2021}, volume={854}, pages={159-173}, doi={10.1016/j.tcs.2020.12.024} } -
Rectilinear link diameter and radius in a rectilinear polygonal domain
, , , , , , , and .Abstract: 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 graph of oriented distances to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in $O (\min(n^\omega, n^2 + nh \log h + \chi^2))$ time, where $\omega<2.373$ denotes the matrix multiplication exponent and $\chi\in \Omega(n)\cap O(n^2)$ is the number of edges of the graph of oriented distances. We also provide an alternative algorithm for computing the diameter that runs in $O(n^2 \log n)$ time.
Computational Geometry: Theory and Applications (CGTA), 92:101685, 2021.
@article{BKRV2021RectilinearLinkJournal, author={Arseneva, Elena and Chiu, Man-Kwun and Korman, Matias and Markovic, Aleksandar and Okamoto, Yoshio and Ooms, Aur\'elien and van Renssen, Andr\'e and Roeloffzen, Marcel}, title={Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain}, journal={Computational Geometry: Theory and Applications (CGTA)}, year={2021}, volume={92}, pages={101685}, doi={10.1016/j.comgeo.2020.101685} } -
Symmetric assembly puzzles are hard, beyond a few pieces
, , , , , , , , and .Abstract: We study the complexity of symmetric assembly puzzles: given a collection of simple polygons, can we translate, rotate, and possibly flip them so that their interior-disjoint union is line symmetric? On the negative side, we show that the problem is strongly NP-complete even if the pieces are all polyominos. On the positive side, we show that the problem can be solved in polynomial time if the number of pieces is a fixed constant.
Computational Geometry: Theory and Applications (CGTA), 90:101648, 2020.
@article{DKKMORRUU2019PuzzleJournal, author={Demaine, Erik D. and Korman, Matias and Ku, Jason S. and Mitchell, Joseph and Otachi, Yota and van Renssen, Andr\'e and Roeloffzen, Marcel and Uehara, Ryuhei and Uno, Yushi}, title={Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces}, journal={Computational Geometry: Theory and Applications (CGTA)}, year={2020}, volume={90}, pages={101648}, doi={10.1016/j.comgeo.2020.101648} } -
Routing in polygonal domains
, , , , , , , , , and .Abstract: We consider the problem of routing a data packet through the visibility graph of a polygonal domain $P$ with $n$ vertices and $h$ holes. We may preprocess $P$ to obtain a label and a routing table for each vertex of $P$. Then, we must be able to route a data packet between any two vertices $p$ and $q$ of $P$, where each step must use only the label of the target node $q$ and the routing table of the current node.For any fixed $\varepsilon > 0$, we present a routing scheme that always achieves a routing path whose length exceeds the shortest path by a factor of at most $1 + \varepsilon$. The labels have $O(\log n)$ bits, and the routing tables are of size $O((\varepsilon^-1+h)\log n)$. The preprocessing time is $O(n^2\log n)$. It can be improved to $O(n^2)$ for simple polygons.
Computational Geometry: Theory and Applications (CGTA) special issue of EuroCG 2017, 87:101593, 2020.
@article{BKMRRSSVW2019RoutingJournal, author={Banyassady, Bahareh and Chiu, Man-Kwun and Korman, Matias and Mulzer, Wolfgang and van Renssen, Andr\'e and Roeloffzen, Marcel and Seiferth, Paul and Stein, Yannik and Vogtenhuber, Birgit and Willert, Max}, title={Routing in Polygonal Domains}, journal={Computational Geometry: Theory and Applications (CGTA) special issue of EuroCG 2017}, year={2020}, volume={87}, pages={101593}, doi={10.1016/j.comgeo.2019.101593} } -
Balanced line separators of unit disk graphs
, , , , , , , , and .Abstract: 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 halfplanes determined by $\ell$ contains at most $2n/3$ unit disks from the set, where $m$ is the number of intersecting pairs of disks. We also show that an axis-parallel line intersecting $O(\sqrt{m+n})$ disks exists, but each halfplane may contain up to $4n/5$ disks. We give an almost tight lower bound (up to sublogarithmic factors) for our approach, and also show that no line-separator of sublinear size in $n$ exists when we look at disks of arbitrary radii, even when $m=0$. Proofs are constructive and suggest simple algorithms that run in linear time. Experimental evaluation has also been conducted, which shows that for random instances our method outperforms the method by Fox and Pach (whose separator has size $O(\sqrt{m})$).
Computational Geometry: Theory and Applications (CGTA), 86:101575, 2020.
@article{CCKKORRSS2020LineSeparatorJournal, author={Carmi, Paz and Chiu, Man-Kwun and Katz, Matya and Korman, Matias and Okamoto, Yoshio and van Renssen, Andr\'e and Roeloffzen, Marcel and Shiitada, Taichi and Smorodinsky, Shakhar}, title={Balanced Line Separators of Unit Disk Graphs}, journal={Computational Geometry: Theory and Applications (CGTA)}, year={2020}, volume={86}, pages={101575}, doi={10.1016/j.comgeo.2019.101575} } -
Spanning properties of Yao and $\Theta$-graphs in the presence of constraints
and .Abstract: We present improved upper bounds on the spanning ratio of constrained $\theta$-graphs with at least 6 cones and constrained Yao-graphs with 5 or at least 7 cones. Given a set of points in the plane, a Yao-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $\theta = 2 \pi/m$, and adds an edge to the closest vertex in each cone. Constrained Yao-graphs have the additional property that no edge properly intersects any of the given line segment constraints. Constrained $\theta$-graphs are similar to constrained Yao-graphs, but use a different method to determine the closest vertex.We present tight bounds on the spanning ratio of a large family of constrained $\theta$-graphs. We show that constrained $\theta$-graphs with $4k + 2$ ($k \geq 1$ and integer) cones have a tight spanning ratio of $1 + 2 \sin(\theta/2)$, where $\theta$ is $2 \pi / (4k + 2)$. We also present improved upper bounds on the spanning ratio of the other families of constrained $\theta$-graphs. These bounds match the current upper bounds in the unconstrained setting.
We also show that constrained Yao-graphs with an even number of cones ($m \geq 8$) have spanning ratio at most $1 / \left( 1 - 2 \sin (\theta/2) \right)$ and constrained Yao-graphs with an odd number of cones ($m \geq 5$) have spanning ratio at most $1 / \left( 1 - 2 \sin (3\theta/8) \right)$. As is the case with constrained $\theta$-graphs, these bounds match the current upper bounds in the unconstrained setting, which implies that like in the unconstrained setting using more cones can make the spanning ratio worse.
International Journal of Computational Geometry & Applications (IJCGA), 29(02):95–120, 2019.
@article{BR2019Constrained, author={Bose, Prosenjit and van Renssen, Andr\'e}, title={Spanning Properties of {Y}ao and $\Theta$-Graphs in the Presence of Constraints}, journal={International Journal of Computational Geometry & Applications (IJCGA)}, year={2019}, volume={29}, number={02}, pages={95-120}, doi={10.1142/S021819591950002X} } -
Geometry and generation of a new graph planarity game
, , , and .Abstract: We introduce a new abstract graph game, Swap Planarity, where the goal is to reach a state without edge intersections and a move consists of swapping the locations of two vertices connected by an edge. We analyze this puzzle game using concepts from graph theory and graph drawing, computational geometry, and complexity. Furthermore, we specify quality criteria for puzzle instances, and describe a method to generate high-quality instances. We also report on experiments that show how well this generation process works.
Journal of Graph Algorithms and Applications (JGAA), 23(4):603–624, 2019.
@article{KKMR2019PlanarityGameJournal, author={Kraaijer, Rutger and van Kreveld, Marc and Meulemans, Wouter and van Renssen, Andr\'e}, title={Geometry and Generation of a new Graph Planarity Game}, journal={Journal of Graph Algorithms and Applications (JGAA)}, year={2019}, volume={23}, number={4}, pages={603-624}, doi={10.7155/jgaa.00504} } -
Fully-dynamic and kinetic conflict-free coloring of intervals with respect to points
, , , , , and .Abstract: We introduce the fully-dynamic conflict-free coloring problem for a set $S$ of intervals in$\mathbb{R}^1$ with respect to points, where the goal is to maintain a conflict-free coloring for $S$ under insertions and deletions. A coloring is conflict-free if for each point $p$ contained in some interval, $p$ is contained in an interval whose color is not shared with any other interval containing $p$. We investigate trade-offs between the number of colors used and the number of intervals that are recolored upon insertion or deletion of an interval. Our results include:- a lower bound on the number of recolorings as a function of the number of colors, which implies that with $O(1)$ recolorings per update the worst-case number of colors is $\Omega(\log n/\log\log n)$, and that any strategy using $O(1/\epsilon)$ colors needs $\Omega(\epsilon n^{\epsilon})$ recolorings;
- a coloring strategy that uses $O(\log n)$ colors at the cost of $O(\log n)$ recolorings, and another strategy that uses $O(1/\epsilon)$ colors at the cost of $O(n^{\epsilon}/\epsilon)$ recolorings;
- stronger upper and lower bounds for special cases.
International Journal of Computational Geometry & Applications (IJCGA) special issue of ISAAC 2017, 29(01):49–72, 2019.
@article{BLMRRW2019ColoringJournal, author={de Berg, Mark and Leijsen, Tim and Markovic, Aleksandar and van Renssen, Andr\'e and Roeloffzen, Marcel and Woeginger, Gerhard}, title={Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points}, journal={International Journal of Computational Geometry & Applications (IJCGA) special issue of ISAAC 2017}, year={2019}, volume={29}, number={01}, pages={49-72}, doi={10.1142/S021819591940003X} } -
Packing plane spanning graphs with short edges in complete geometric graphs
, , , , , , , and .Abstract: Given a set of points in the plane, we want to establish a connected spanning graph between these points, called connection network, that consists of several disjoint layers. Motivated by sensor networks, our goal is that each layer is connected, spanning, and plane. No edge in this connection network is too long in comparison to the length needed to obtain a spanning tree.We consider two different approaches. First we show an almost optimal centralized approach to extract two layers. Then we consider a distributed model in which each point can compute its adjacencies using only information about vertices at most a predefined distance away. We show a constant factor approximation with respect to the length of the longest edge in the graphs. In both cases the obtained layers are plane.
Computational Geometry: Theory and Applications (CGTA), 82:1–15, 2019.
@article{AHKPRRRV2019SpanningTreesJournal, author={Aichholzer, Oswin and Hackl, Thomas and Korman, Matias and Pilz, Alexander and van Renssen, Andr\'e and Roeloffzen, Marcel and Rote, Gunter and Vogtenhuber, Birgit}, title={Packing Plane Spanning Graphs with Short Edges in Complete Geometric Graphs}, journal={Computational Geometry: Theory and Applications (CGTA)}, year={2019}, volume={82}, pages={1-15}, doi={10.1016/j.comgeo.2019.04.001} } -
Faster algorithms for growing prioritized disks and rectangles
, , , , , , , , and .Abstract: Motivated by map labeling, Funke, Krumpe, and Storandt [IWOCA 2016] introduced the following problem: we are given a sequence of $n$ disks in the plane. Initially, all disks have radius $0$, and they grow at constant, but possibly different, speeds. Whenever two disks touch, the one with the higher index disappears. The goal is to determine the elimination order,i.e., the order in which the disks disappear. We provide the first general subquadratic algorithm for this problem. Our solution extends to other shapes (e.g., rectangles), and it works in any fixed dimension.We also describe an alternative algorithm that is based on quadtrees. Its running time is $O\big(n \big(\log n + \min { \log \Delta, \log \Phi }\big)\big)$, where $\Delta$ is the ratio of the fastest and the slowest growth rate and $\Phi$ is the ratio of the largest and the smallest distance between two disk centers. This improves the running times of previous algorithms by Funke, Krumpe, and Storandt [IWOCA 2016], Bahrdt et al. [ALENEX 2017], and Funke and Storandt [EuroCG 2017].
Finally, we give an $\Omega(n\log n)$ lower bound, showing that our quadtree algorithms are almost tight.
Computational Geometry: Theory and Applications (CGTA), 80:23–39, 2019.
@article{DKRR2019GrowingDisksJournal, author={Ahn, Hee-Kap and Bae, Sang Won and Choi, Jongmin and Korman, Matias and Mulzer, Wolfgang and Oh, Eunjin and Park, Ji-won and van Renssen, Andr\'e and Vigneron, Antoine}, title={Faster Algorithms for Growing Prioritized Disks and Rectangles}, journal={Computational Geometry: Theory and Applications (CGTA)}, year={2019}, volume={80}, pages={23-39}, doi={10.1016/j.comgeo.2019.02.001} } -
On plane constrained bounded-degree spanners
, , , and .Abstract: Let $P$ be a finite set of points in the plane and $S$ a set of non-crossing line segments with endpoints in $P$. The visibility graph of $P$ with respect to $S$, denoted $Vis(P,S)$, has vertex set $P$ and an edge for each pair of vertices $u,v$ in $P$ for which no line segment of $S$ properly intersects $uv$. We show that the constrained half-$\theta_6$-graph (which is identical to the constrained Delaunay graph whose empty visible region is an equilateral triangle) is a plane 2-spanner of $Vis(P,S)$. We then show how to construct a plane 6-spanner of $Vis(P,S)$ with maximum degree $6+c$, where $c$ is the maximum number of segments of $S$ incident to a vertex.
Algorithmica, 81(4):1392–1415, 2019.
@article{BFRV2019ConstrainedBoundedJournal, author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander}, title={On Plane Constrained Bounded-Degree Spanners}, journal={Algorithmica}, year={2019}, volume={81}, number={4}, pages={1392-1415}, doi={10.1007/s00453-018-0476-8} } -
Dynamic graph coloring
, , , , , , and .Abstract: 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-offs between the number of recolorings and the number of colors used. For any $d>0$, the first algorithm maintains a proper $O(\mathcal{C} d N^{1/d})$-coloring while recoloring at most $O(d)$ vertices per update, where $\mathcal{C}$ and $N$ are the maximum chromatic number and maximum number of vertices, respectively. The second algorithm reverses the trade-off, maintaining an $O(\mathcal{C} d)$-coloring with $O(d N^{1/d})$ recolorings per update. The two converge when $d = \log N$, maintaining an $O(\mathcal{C} \log N)$-coloring with $O(\log N)$ recolorings per update. We also present a lower bound, showing that any algorithm that maintains a $c$-coloring of a $2$-colorable graph on $N$ vertices must recolor at least $\Omega(N^\frac2c(c-1))$ vertices per update, for any constant $c \geq 2$.
Algorithmica, 81(4):1319–1341, 2019.
@article{BCKLRRV2019ColoringJournal, author={Barba, Luis and Cardinal, Jean and Korman, Matias and Langerman, Stefan and van Renssen, Andr\'e and Roeloffzen, Marcel and Verdonschot, Sander}, title={Dynamic Graph Coloring}, journal={Algorithmica}, year={2019}, volume={81}, number={4}, pages={1319-1341}, doi={10.1007/s00453-018-0473-y} } -
Routing on the visibility graph
, , , and .Abstract: We consider the problem of routing on a network in the presence of line segment constraints (i.e., obstacles that edges in our network are not allowed to cross). Let $P$ be a set of $n$ points in the plane and let $S$ be a set of non-crossing line segments whose endpoints are in $P$. We present two deterministic 1-local $O(1)$-memory routing algorithms that are guaranteed to find a path of at most linear size between any pair of vertices of the visibility graph of $P$ with respect to a set of constraints $S$ (i.e., the algorithms never look beyond the direct neighbours of the current location and store only a constant amount of additional information). Contrary to all existing deterministic local routing algorithms, our routing algorithms do not route on a plane subgraph of the visibility graph. Additionally, we provide lower bounds on the routing ratio of any deterministic local routing algorithm on the visibility graph.
Journal of Computational Geometry (JoCG), 9(1):430–453, 2018.
@article{BKRV2018RoutingVisibilityGraphJournal, author={Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Verdonschot, Sander}, title={Routing on the Visibility Graph}, journal={Journal of Computational Geometry (JoCG)}, year={2018}, volume={9}, number={1}, pages={430–453}, doi={10.20382/jocg.v9i1a15} } -
Constrained generalized Delaunay graphs are plane spanners
, , and .Abstract: We look at generalized Delaunay graphs in the constrained setting by introducing line segments which the edges of the graph are not allowed to cross. Given an arbitrary convex shape $C$, a constrained Delaunay graph is constructed by adding an edge between two vertices $p$ and $q$ if and only if there exists a homothet of $C$ with $p$ and $q$ on its boundary that does not contain any other vertices visible to $p$ and $q$. We show that, regardless of the convex shape $C$ used to construct the constrained Delaunay graph, there exists a constant $t$ (that depends on $C$) such that it is a plane $t$-spanner of the visibility graph. Furthermore, we reduce the upper bound on the spanning ratio for the special case where the empty convex shape is an arbitrary rectangle to $\sqrt{2} \cdot \left( 2 l/s + 1 \right)$, where $l$ and $s$ are the length of the long and short side of the rectangle.
Computational Geometry: Theory and Applications (CGTA), 74:50–65, 2018.
@article{BCR2018GeneralizedDelaunayJournal, author={Bose, Prosenjit and De Carufel, Jean-Lou and van Renssen, Andr\'e}, title={Constrained Generalized {D}elaunay Graphs Are Plane Spanners}, journal={Computational Geometry: Theory and Applications (CGTA)}, year={2018}, volume={74}, pages={50-65}, doi={10.1016/j.comgeo.2018.06.006} } -
Time-space trade-offs for triangulations and Voronoi diagrams
, , , , , and .Abstract: Let $S$ be a planar $n$-point set. A triangulation for $S$ is a maximal plane straight-line graph with vertex set $S$. The Voronoi diagram for $S$ is the subdivision of the plane into cells such that each cell has the same nearest neighbors in $S$. Classically, both structures can be computed in $O(n \log n)$ time and $O(n)$ space. We study the situation when the available workspace is limited: given a parameter $s \in {1, \dots, n}$, an $s$-workspace algorithm has read-only access to an input array with the points from $S$ in arbitrary order, and it may use only $O(s)$ additional words of $\Theta(\log n)$ bits for reading and writing intermediate data. The output should then be written to a write-only structure. We describe a deterministic $s$-workspace algorithm for computing a triangulation of $S$ in time $O(n^2/s + n \log n \log s )$ and a randomized $s$-workspace algorithm for finding the Voronoi diagram of $S$ in expected time $O((n^2/s) \log s + n \log s \log^*s)$.
Computational Geometry: Theory and Applications (CGTA) special issue of EuroCG 2015, 73:35–45, 2018.
@article{KMRRSS2018VoronoiJournal, author={Korman, Matias and Mulzer, Wolfgang and van Renssen, Andr\'e and Roeloffzen, Marcel and Seiferth, Paul and Stein, Yannik}, title={Time-Space Trade-offs for Triangulations and {V}oronoi Diagrams}, journal={Computational Geometry: Theory and Applications (CGTA) special issue of EuroCG 2015}, year={2018}, volume={73}, pages={35-45}, doi={10.1016/j.comgeo.2017.01.001} } -
Improved time-space trade-offs for computing Voronoi diagrams
, , , , , , and .Abstract: Let $P$ be a planar set of $n$ sites in general position. For $k \in {1, \dots, n-1}$, the Voronoi diagram of order $k$ for $P$ is obtained by subdividing the plane into cells such that points in the same cell have the same set of nearest $k$ neighbors in $P$. The (nearest site) Voronoi diagram ($NVD$) and the farthest site Voronoi diagram ($FVD$) are the particular cases of $k=1$ and $k=n-1$, respectively. For any given $K \in {1, \dots, n-1}$, the family of all higher-order Voronoi diagrams of order $k = 1, \dots, K$ for $P$ can be computed in total time $O(nK^2+ n \log n)$ using $O(K^2(n-K))$ space [Aggarwal et al., DCG’89; Lee, TC’82]. Moreover, $NVD$ and $FVD$ for $P$ can be computed in $O(n\log n)$ time using $O(n)$ space [Preparata, Shamos, Springer’85].For $s \in {1, \dots, n}$, an $s$-workspace algorithm has random access to a read-only array with the sites of $P$ in arbitrary order. Additionally, the algorithm may use $O(s)$ words, of $\Theta(\log n)$ bits each, for reading and writing intermediate data. The output can be written only once and cannot be accessed or modified afterwards.
We describe a deterministic $s$-workspace algorithm for computing $NVD$ and $FVD$ for $P$ that runs in $O((n^2/s)\log s)$ time. Moreover, we generalize our $s$-workspace algorithm so that for any given $K \in {1, \dots, O(\sqrt{s})}$, we compute the family of all higher-order Voronoi diagrams of order $k = 1, \dots, K$ for $P$ in total expected time $O\bigl(\frac{n^2 K^5}{s}(\log s + K \, 2^{O(\log^* K)}) \bigr)$ or in total deterministic time $O\bigl(\frac{n^2 K^5}{s}(\log s + K \log K) \bigr)$. Previously, for Voronoi diagrams, the only known $s$-workspace algorithm runs in expected time $O\bigl((n^2/s) \log s + n \log s \log^*s\bigr)$ [Korman et al., WADS’15] and only works for $NVD$ (i.e., $k=1$). Unlike the previous algorithm, our new method is very simple and does not rely on advanced data structures or random sampling techniques.
Journal of Computational Geometry (JoCG), 9(1):191–212, 2018.
@article{BKRV2018VoronoiJournal, author={Banyassady, Bahareh and Korman, Matias and Mulzer, Wolfgang and van Renssen, Andr\'e and Roeloffzen, Marcel and Seiferth, Paul and Stein, Yannik}, title={Improved Time-Space Trade-offs for Computing {V}oronoi Diagrams}, journal={Journal of Computational Geometry (JoCG)}, year={2018}, volume={9}, number={1}, pages={191-212}, doi={10.20382/jocg.v9i1a6} } -
Continuous Yao graphs
, , , , , , , , , and .Abstract: In this paper, we introduce a variation of the well-studied Yao graphs. Given a set of points $S\subset \mathbb{R}^2$ and an angle $0 < \theta \leq 2\pi$, we define the continuous Yao graph $cY(\theta)$ with vertex set $S$ and angle $\theta$ as follows. For each $p,q\in S$, we add an edge from $p$ to $q$ in $cY(\theta)$ if there exists a cone with apex $p$ and aperture $\theta$ such that $q$ is a closest point to $p$ inside this cone.We study the spanning ratio of $cY(\theta)$ for different values of $\theta$. Using a new algebraic technique, we show that $cY(\theta)$ is a spanner when $\theta \leq 2\pi /3$. We believe that this technique may be of independent interest. We also show that $cY(\pi)$ is not a spanner, and that $cY(\theta)$ may be disconnected for $\theta > \pi$. Furthermore, we show that $cY(\theta)$ is a region-fault-tolerant geometric spanner for convex fault regions when $\theta<\pi/3$. For half-plane faults, $cY(\theta)$ remains connected if $\theta<\pi$. Finally, we show that $cY(\theta)$ is not always self-approaching for any value of $\theta$.
Computational Geometry: Theory and Applications (CGTA), 67:42–52, 2018.
@article{BBBCDFFRTV2018Continuous, author={Bakhshesh, Davood and Barba, Luis and Bose, Prosenjit and De Carufel, Jean-Lou and Damian, Mirela and Fagerberg, Rolf and Farshi, Mohammad and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander}, title={Continuous {Y}ao Graphs}, journal={Computational Geometry: Theory and Applications (CGTA)}, year={2018}, volume={67}, pages={42-52}, doi={10.1016/j.comgeo.2017.10.002} } -
Upper and lower bounds for online routing on Delaunay triangulations
, , , , and .Abstract: Consider a weighted graph $G$ whose vertices are points in the plane and edges are line segments between pairs of points. The weight of each edge is the Euclidean distance between its two endpoints. A routing algorithm on $G$ has a competitive ratio of $c$ if the length of the path produced by the algorithm from any vertex $s$ to any vertex $t$ is at most $c$ times the length of the shortest path from $s$ to $t$ in $G$. If the length of the path is at most $c|[st]|$ (where $|[st]|$ is the length of the line segment $[st]$), we say that the routing algorithm has a routing ratio of $c$. The routing algorithm is online if it makes forwarding decisions based on 1) the $k$-neighborhood in $G$ (for some integer constant $k>0$) of the current position of the message and 2) limited information stored in the message header.We present an online routing algorithm on the Delaunay triangulation with routing ratio less than $5.90$. This improves upon the algorithm with best known routing ratio of $15.48$. The algorithm is an adaptation, to the Delaunay triangulation, of the classic routing algorithm by Chew on the $L_1$-Delaunay triangulation. It makes forwarding decisions based on the $1$-neighborhood of the current position of the message and the positions of the message source and destination only. This last requirement is an improvement over the best known online routing algorithms on the Delaunay triangulation which require the header of a message to also contain partial sums of distances along the routing path.
We show that the routing ratio of Chew’s algorithm on the Delaunay triangulation can be greater than $5.7282$ so the $5.90$ upper bound is close to best possible. We also show that the routing (resp., competitive) ratios of any deterministic $k$-local algorithm is at least $1.70$ (resp., $1.33$) for the Delaunay triangulation and $2.70$ (resp. $1.12$) for the $L_1$-Delaunay triangulation. In the case of the $L_1$-Delaunay triangulation, this implies that even though there always exists a path between $s$ and $t$ whose length is at most $2.61|[st]|$, it is not always possible to route a message along a path of length less than $2.70|[st]|$.
Discrete & Computational Geometry (DCG), 58(2):482–504, 2017.
@article{BBCPR2017DelaunayJournal, author={Bonichon, Nicolas and Bose, Prosenjit and De Carufel, Jean-Lou and Perkovi\'c, Ljubomir and van Renssen, Andr\'e}, title={Upper and Lower Bounds for Online Routing on {D}elaunay Triangulations}, journal={Discrete & Computational Geometry (DCG)}, year={2017}, volume={58}, number={2}, pages={482-504}, doi={10.1007/s00454-016-9842-y} } -
Competitive local routing with constraints
, , , and .Abstract: Let $P$ be a set of $n$ vertices in the plane and $S$ a set of non-crossing line segments between vertices in $P$, called constraints. Two vertices are visible if the straight line segment connecting them does not properly intersect any constraints. The constrained $\Theta_m$-graph is constructed by partitioning the plane around each vertex into $m$ disjoint cones, each with aperture $\theta = 2 \pi/m$, and adding an edge to the ‘closest’ visible vertex in each cone. We consider how to route on the constrained $\Theta_6$-graph. We first show that no deterministic 1-local routing algorithm is $o(\sqrt{n})$-competitive on all pairs of vertices of the constrained $\Theta_6$-graph. After that, we show how to route between any two visible vertices of the constrained $\Theta_6$-graph using only 1-local information. Our routing algorithm guarantees that the returned path is 2-competitive. Additionally, we provide a 1-local 18-competitive routing algorithm for visible vertices in the constrained half-$\Theta_6$-graph, a subgraph of the constrained $\Theta_6$-graph that is equivalent to the Delaunay graph where the empty region is an equilateral triangle. To the best of our knowledge, these are the first local routing algorithms in the constrained setting with guarantees on the length of the returned path.
Journal of Computational Geometry (JoCG), 8(1):125–152, 2017.
@article{BFRV2017RoutingJournal, author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander}, title={Competitive Local Routing with Constraints}, journal={Journal of Computational Geometry (JoCG)}, year={2017}, volume={8}, number={1}, pages={125-152}, doi={10.20382/jocg.v8i1a7} } -
Time-space trade-off algorithms for triangulating a simple polygon
, , , , and .Abstract: An $s$-workspace algorithm is an algorithm that has read-only access to the values of the input, write-only access to the output, and only uses $O(s)$ additional words of space. We present a randomized $s$-workspace algorithm for triangulating a simple polygon $P$ of $n$ vertices that runs in $O(n^2/s+n \log n \log^5 (n/s))$ expected time using $O(s)$ variables, for any $s \leq n$. In particular, when $s \leq \frac{n}{\log n\log^{5}\log n$ the algorithm runs in $O(n^2/s)$ expected time.
Journal of Computational Geometry (JoCG), 8(1):105–124, 2017.
@article{AKPRR2017TriangulatingJournal, author={Aronov, Boris and Korman, Matias and Pratt, Simon and van Renssen, Andr\'e and Roeloffzen, Marcel}, title={Time-Space Trade-off Algorithms for Triangulating a Simple Polygon}, journal={Journal of Computational Geometry (JoCG)}, year={2017}, volume={8}, number={1}, pages={105-124}, doi={10.20382/jocg.v8i1a6} } -
On interference among moving sensors and related problems
, , , , , and .Abstract: We show that for any set of $n$ moving points in $\mathbb{R}^d$ and any parameter $2 \le k \le n$, one can select a fixed non-empty subset of the points of size $O(k \log k)$, such that the Voronoi diagram of this subset is ”balanced” at any given time (i.e., it contains $O(n/k)$ points per cell). We also show that the bound $O(k \log k)$ is near optimal even for the one dimensional case in which points move linearly in time. As an application, we show that one can assign communication radii to the sensors of a network of $n$ moving sensors so that at any given time, their interference is $O(\sqrt{n\log n})$. This is optimal up to an $O(\sqrt{\log n})$ factor. In order to obtain these results, we extend well-known results from $\epsilon$-net theory to kinetic environments.
Journal of Computational Geometry (JoCG), 8(1):32–46, 2017.
@article{CKKRRS2017InterferenceJournal, author={De Carufel, Jean-Lou and Katz, Matya and Korman, Matias and van Renssen, Andr\'e and Roeloffzen, Marcel and Smorodinsky, Shakhar}, title={On interference among moving sensors and related problems}, journal={Journal of Computational Geometry (JoCG)}, year={2017}, volume={8}, number={1}, pages={32-46}, doi={10.20382/jocg.v8i1a3} } -
Hanabi is NP-hard, even for cheaters who look at their cards
, , , , , , , and .Abstract: In this paper we study a cooperative card game called Hanabi from the viewpoint of algorithmic combinatorial game theory. In Hanabi, each card has one among $c$ colors and a number between $1$ and $n$. The aim is to make, for each color, a pile of cards of that color with all increasing numbers from $1$ to $n$. At each time during the game, each player holds $h$ cards in hand. Cards are drawn sequentially from a deck and the players should decide whether to play, discard or store them for future use. One of the features of the game is that the players can see their partners’ cards but not their own and information must be shared through hints.We introduce a single-player, perfect-information model and show that the game is intractable even for this simplified version where we forego both the hidden information and the multiplayer aspect of the game, even when the player can only hold two cards in her hand. On the positive side, we show that the decision version of the problem---to decide whether or not numbers from $1$ through $n$ can be played for every color---can be solved in (almost) linear time for some restricted cases.
Theoretical Computer Science (TCS), 675:43–55, 2017.
@article{BCDKMRRU2017HanabiJournal, author={Baffier, Jean-Francois and Chiu, Man-Kwun and Diez, Yago and Korman, Matias and Mitsou, Valia and van Renssen, Andr\'e and Roeloffzen, Marcel and Uno, Yushi}, title={Hanabi is {NP}-hard, Even for Cheaters who Look at Their Cards}, journal={Theoretical Computer Science (TCS)}, year={2017}, volume={675}, pages={43-55}, doi={10.1016/j.tcs.2017.02.024} } -
The price of order
, , and .Abstract: We present tight bounds on the spanning ratio of a large family of ordered $\theta$-graphs. A $\theta$-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $\theta = 2 \pi/m$. An ordered $\theta$-graph is constructed by inserting the vertices one by one and connecting each vertex to the closest previously-inserted vertex in each cone. We show that for any integer $k \geq 1$, ordered $\theta$-graphs with $4k + 4$ cones have a tight spanning ratio of $1 + 2 \sin(\theta/2) / (\cos(\theta/2) - \sin(\theta/2))$. We also show that for any integer $k \geq 2$, ordered $\theta$-graphs with $4k + 2$ cones have a tight spanning ratio of $1 / (1 - 2 \sin(\theta/2))$. We provide lower bounds for ordered $\theta$-graphs with $4k + 3$ and $4k + 5$ cones. For ordered $\theta$-graphs with $4k + 2$ and $4k + 5$ cones these lower bounds are strictly greater than the worst case spanning ratios of their unordered counterparts. These are the first results showing that ordered $\theta$-graphs have worse spanning ratios than unordered $\theta$-graphs. Finally, we show that, unlike their unordered counterparts, the ordered $\theta$-graphs with 4, 5, and 6 cones are not spanners.
International Journal of Computational Geometry & Applications (IJCGA) special issue of ISAAC 2014, 26(03n04):135–149, 2017.
@article{BMR2017OrderJournal, author={Bose, Prosenjit and Morin, Pat and van Renssen, Andr\'e}, title={The Price of Order}, journal={International Journal of Computational Geometry & Applications (IJCGA) special issue of ISAAC 2014}, year={2017}, volume={26}, number={03n04}, pages={135-149}, doi={10.1142/S0218195916600013} } -
Area-preserving simplification and schematization of polygonal subdivisions
, , , and .Abstract: In this paper, we study automated simplification and schematization of territorial outlines. We present a quadratic-time simplification algorithm based on an operation called an edge-move. We prove that the number of edges of any nonconvex simple polygon can be reduced with this operation. Moreover, edge-moves preserve area and topology and do not introduce new orientations. The latter property in particular makes the algorithm highly suitable for schematization in which all resulting lines are required to be parallel to one of a given set of lines (orientations). To obtain such a result, we need only to preprocess the input to use only lines that are parallel to one of the given set. We present an algorithm to enforce such orientation restrictions, again without changing area or topology. Experiments show that our algorithms obtain results of high visual quality.
ACM Transactions on Spatial Algorithms and Systems (ACM TSAS), 2(1):2:1–2:36, 2016.
@article{BMRS2016Schematization, author={Buchin, Kevin and Meulemans, Wouter and van Renssen, Andr\'e and Speckmann, Bettina}, title={Area-Preserving Simplification and Schematization of Polygonal Subdivisions}, journal={ACM Transactions on Spatial Algorithms and Systems (ACM TSAS)}, year={2016}, volume={2}, number={1}, pages={2:1-2:36}, doi={10.1145/2818373} } -
Towards tight bounds on theta-graphs: More is not always better
, , , , and .Abstract: We present improved upper and lower bounds on the spanning ratio of $\theta$-graphs with at least six cones. Given a set of points in the plane, a $\theta$-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $\theta = 2 \pi/m$, and adds an edge to the ‘closest’ vertex in each cone. We show that for any integer $k \geq 1$, $\theta$-graphs with $4k + 2$ cones have a spanning ratio of $1 + 2 \sin(\theta/2)$ and we provide a matching lower bound, showing that this spanning ratio tight.Next, we show that for any integer $k \geq 1$, $\theta$-graphs with $4k + 4$ cones have spanning ratio at most $1 + 2 \sin(\theta/2) / (\cos(\theta/2) - \sin(\theta/2))$. We also show that $\theta$-graphs with $4k + 3$ and $4k + 5$ cones have spanning ratio at most $\cos (\theta/4) / (\cos (\theta/2) - \sin (3\theta/4))$. This is a significant improvement on all families of $\theta$-graphs for which exact bounds are not known. For example, the spanning ratio of the $\theta$-graph with 7 cones is decreased from at most 7.5625 to at most 3.5132. These spanning proofs also imply improved upper bounds on the competitiveness of the $\theta$-routing algorithm. In particular, we show that the $\theta$-routing algorithm is $(1 + 2 \sin(\theta/2) / (\cos(\theta/2) - \sin(\theta/2)))$-competitive on $\theta$-graphs with $4k + 4$ cones and that this ratio is tight.
Finally, we present improved lower bounds on the spanning ratio of these graphs. Using these bounds, we provide a partial order on these families of $\theta$-graphs. In particular, we show that $\theta$-graphs with $4k + 4$ cones have spanning ratio at least $1 + 2 \tan(\theta/2) + 2 \tan^2(\theta/2)$, where $\theta$ is $2 \pi / (4k + 4)$. This is somewhat surprising since, for equal values of $k$, the spanning ratio of $\theta$-graphs with $4k + 4$ cones is greater than that of $\theta$-graphs with $4k + 2$ cones, showing that increasing the number of cones can make the spanning ratio worse.
Theoretical Computer Science (TCS), 616:70–93, 2016.
@article{BCMRV2016Theta, author={Bose, Prosenjit and De Carufel, Jean-Lou and Morin, Pat and van Renssen, Andr\'e and Verdonschot, Sander}, title={Towards Tight Bounds on Theta-Graphs: {M}ore is not Always Better}, journal={Theoretical Computer Science (TCS)}, year={2016}, volume={616}, pages={70-93}, doi={10.1016/j.tcs.2015.12.017} } -
Optimal local routing on Delaunay triangulations defined by empty equilateral triangles
, , , and .Abstract: We present a deterministic local routing algorithm that is guaranteed to find a path between any pair of vertices in a half-$\theta_6$-graph (the half-$\theta_6$-graph is equivalent to the Delaunay triangulation where the empty region is an equilateral triangle). The length of the path is at most $5/\sqrt{3} \approx 2.887$ times the Euclidean distance between the pair of vertices. Moreover, we show that no local routing algorithm can achieve a better routing ratio, thereby proving that our routing algorithm is optimal. This is somewhat surprising because the spanning ratio of the half-$\theta_6$-graph is 2, meaning that even though there always exists a path whose lengths is at most twice the Euclidean distance, we cannot always find such a path when routing locally.Since every triangulation can be embedded in the plane as a half-$\theta_6$-graph using $O(\log n)$ bits per vertex coordinate via Schnyder’s embedding scheme (SODA 1990), our result provides a competitive local routing algorithm for every such embedded triangulation. Finally, we show how our routing algorithm can be adapted to provide a routing ratio of $15/\sqrt{3} \approx 8.660$ on two bounded degree subgraphs of the half-$\theta_6$-graph.
SIAM Journal on Computing (SICOMP), 44(6):1626–1649, 2015.
@article{BFRV2015RoutingJournal, author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander}, title={Optimal local routing on {D}elaunay triangulations defined by empty equilateral triangles}, journal={SIAM Journal on Computing (SICOMP)}, year={2015}, volume={44}, number={6}, pages={1626-1649}, doi={10.1137/140988103} } -
New and improved spanning ratios for Yao graphs
, , , , , , , , , and .Abstract: For a set of points in the plane and a fixed integer $k > 0$, the Yao graph $Y_k$ partitions the space around each point into $k$ equiangular cones of angle $\theta=2\pi/k$, and connects each point to a nearest neighbor in each cone. It is known for all Yao graphs, with the sole exception of $Y_5$, whether or not they are geometric spanners. In this paper we close this gap by showing that for odd $k \geq 5$, the spanning ratio of $Y_k$ is at most $1/(1-2\sin(3\theta/8))$, which gives the first constant upper bound for $Y_5$, and is an improvement over the previous bound of $1/(1-2\sin(\theta/2))$ for odd $k \geq 7$.We further reduce the upper bound on the spanning ratio for $Y_5$ from $10.9$ to $2+\sqrt{3} \approx 3.74$, which falls slightly below the lower bound of $3.79$ established for the spanning ratio of $\Theta_5$ ($\Theta$-graphs differ from Yao graphs only in the way they select the closest neighbor in each cone). This is the first such separation between a Yao and $\Theta$-graph with the same number of cones. We also give a lower bound of $2.87$ on the spanning ratio of $Y_5$.
In addition, we revisit the $Y_6$ graph, which plays a particularly important role as the transition between the graphs ($k > 6$) for which simple inductive proofs are known, and the graphs ($k \le 6$) whose best spanning ratios have been established by complex arguments. Here we reduce the known spanning ratio of $Y_6$ from $17.6$ to $5.8$, getting closer to the spanning ratio of 2 established for $\Theta_6$.
Finally, we present the first lower bounds on the spanning ratio of Yao graphs with more than six cones, and a construction that shows that the Yao-Yao graph (a bounded-degree variant of the Yao graph) with five cones is not a spanner.
Journal of Computational Geometry (JoCG) special issue for SoCG 2014, 6(2):19–53, 2015.
@article{BBDFKORTVX2015YaoJournal, author={Barba, Luis and Bose, Prosenjit and Damian, Mirela and Fagerberg, Rolf and Keng, Wah Loon and O'Rourke, Joseph and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander and Xia, Ge}, title={New and Improved Spanning Ratios for {Y}ao Graphs}, journal={Journal of Computational Geometry (JoCG) special issue for SoCG 2014}, year={2015}, volume={6}, number={2}, pages={19-53}, doi={10.20382/jocg.v6i2a3} } -
The $\theta_5$-graph is a spanner
, , , and .Abstract: Given a set of points in the plane, we show that the $\theta$-graph with 5 cones is a geometric spanner with spanning ratio at most $\sqrt{50 + 22 \sqrt{5}} \approx 9.960$. This is the first constant upper bound on the spanning ratio of this graph. The upper bound uses a constructive argument that gives a (possibly self-intersecting) path between any two vertices, of length at most $\sqrt{50 + 22 \sqrt{5}}$ times the Euclidean distance between the vertices. We also give a lower bound on the spanning ratio of $\frac{1}{2}(11\sqrt{5} -17) \approx 3.798$.
Computational Geometry: Theory and Applications (CGTA), 48(2):108–119, 2015.
@article{BMRV2015Theta5Journal, author={Bose, Prosenjit and Morin, Pat and van Renssen, Andr\'e and Verdonschot, Sander}, title={The $\theta_5$-graph is a spanner}, journal={Computational Geometry: Theory and Applications (CGTA)}, year={2015}, volume={48}, number={2}, pages={108--119}, doi={10.1016/j.comgeo.2014.08.005} } -
Theta-3 is connected
, , , , , , , and .Abstract: In this paper, we show that the $\theta$-graph with three cones is connected. We also provide an alternative proof of the connectivity of the Yao graph with three cones.
Computational Geometry: Theory and Applications (CGTA) special issue for CCCG 2013, 47(9):910–917, 2014.
@article{ABBBKRTV2014Theta3Journal, author={Aichholzer, Oswin and Bae, Sang Won and Barba, Luis and Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander}, title={Theta-3 is connected}, journal={Computational Geometry: Theory and Applications (CGTA) special issue for CCCG 2013}, year={2014}, volume={47}, number={9}, pages={910--917}, doi={10.1016/j.comgeo.2014.05.001} } -
Making triangulations 4-connected using flips
, , , , and .Abstract: We show that any combinatorial triangulation on $n$ vertices can be transformed into a 4-connected one using at most $\lfloor(3n - 9)/5\rfloor$ edge flips. We also give an example of an infinite family of triangulations that requires this many flips to be made 4-connected, showing that our bound is tight. In addition, for $n \geq 19$, we improve the upper bound on the number of flips required to transform any 4-connected triangulation into the canonical triangulation (the triangulation with two dominant vertices), matching the known lower bound of $2n - 15$. Our results imply a new upper bound on the diameter of the flip graph of $5.2 n - 33.6$, improving on the previous best known bound of $6n - 30$.
Computational Geometry: Theory and Applications (CGTA) special issue for CCCG 2011, 47(2, Part A):187–197, 2014.
@article{BJRSV2014Triangulations, author={Bose, Prosenjit and Jansens, Dana and van Renssen, Andr\'e and Saumell, Maria and Verdonschot, Sander}, title={Making triangulations 4-connected using flips}, journal={Computational Geometry: Theory and Applications (CGTA) special issue for CCCG 2011}, year={2014}, volume={47}, number={2, Part A}, pages={187--197}, doi={10.1016/j.comgeo.2012.10.012} }
Peer Reviewed Conference Papers
Conference papers that I presented are marked with 
.
(Icon by Double-J Design, used under a Creative Commons Attribution license)
-
Computing a subtrajectory cluster from $c$-packed trajectories
, , , and .Abstract: We present a near-linear time approximation algorithm for the subtrajectory cluster problem of $c$-packed trajectories. Given a trajectory $T$ of complexity $n$, an approximation factor $\varepsilon$, and a desired distance $d$, the problem involves finding $m$ subtrajectories of $T$ such that their pair-wise Fréchet distance is at most $(1 + \varepsilon)d$. At least one subtrajectory must be of length $l$ or longer. A trajectory $T$ is $c$-packed if the intersection of $T$ and any ball $B$ with radius $r$ is at most $c \cdot r$ in length.Previous results by Gudmundsson and Wong [J. Gudmundsson and S. Wong. Cubic upper and lower bounds for subtrajectory clustering under the continuous Fréchet distance. SODA, pages 173-189, 2022] established an $\Omega(n^3)$ lower bound unless the Strong Exponential Time Hypothesis fails, and they presented an $O(n^3 \log^2 n)$ time algorithm. We circumvent this conditional lower bound by studying subtrajectory cluster on $c$-packed trajectories, resulting in an algorithm with an $O((c^2 n/\varepsilon^2)\log(c/\varepsilon)\log(n/\varepsilon))$ time complexity.
In Proceedings of the 34th International Symposium on Algorithms and Computation (ISAAC 2023), volume 283 of Leibniz International Proceedings in Informatics, pages 34:1–34:15, 2023.
@inproceedings{GHRW2023Cluster, author={Gudmundsson, Joachim and Huang, Zijin and van Renssen, Andr\'e and Wong, Sampson}, title={Computing a Subtrajectory Cluster from $c$-Packed Trajectories}, booktitle={Proceedings of the 34th International Symposium on Algorithms and Computation (ISAAC 2023)}, year={2023}, volume={283}, series={Leibniz International Proceedings in Informatics}, pages={34:1-34:15}, doi={10.4230/LIPIcs.ISAAC.2023.34} } -
The tight spanning ratio of the rectangle Delaunay triangulation
, , , and .Abstract: Spanner construction is a well-studied problem and Delaunay triangulations are among the most popular spanners. Tight bounds are known if the Delaunay triangulation is constructed using an equilateral triangle, a square, or a regular hexagon. However, all other shapes have remained elusive. In this paper we extend the restricted class of spanners for which tight bounds are known. We prove that Delaunay triangulations constructed using rectangles with aspect ratio $A$ have spanning ratio at most $\sqrt{2} \sqrt{1+A^2 + A \sqrt{A^2 + 1}}$, which matches the known lower bound.
In Proceedings of the 31st European Symposium on Algorithms (ESA 2023), volume 274 of Leibniz International Proceedings in Informatics, pages 99:1–99:15, 2023.
@inproceedings{RSSW2023RectangleDelaunayTight, author={van Renssen, Andr\'e and Sha, Yuan and Sun, Yucheng and Wong, Sampson}, title={The Tight Spanning Ratio of the Rectangle {D}elaunay Triangulation}, booktitle={Proceedings of the 31st European Symposium on Algorithms (ESA 2023)}, year={2023}, volume={274}, series={Leibniz International Proceedings in Informatics}, pages={99:1-99:15}, doi={10.4230/LIPIcs.ESA.2023.99} } -
Oriented spanners
, , , , , , and .Abstract: Given a point set $P$ in the Euclidean plane and a parameter $t$, we define an oriented $t$-spanner as an oriented subgraph of the complete bi-directed graph such that for every pair of points, the shortest cycle in $G$ through those points is at most a factor $t$ longer than the shortest oriented cycle in the complete bi-directed graph. We investigate the problem of computing sparse graphs with small oriented dilation.As we can show that minimising oriented dilation for a given number of edges is NP-hard in the plane, we first consider one-dimensional point sets. While obtaining a $1$-spanner in this setting is straightforward, already for five points such a spanner has no plane embedding with the leftmost and rightmost point on the outer face. This leads to restricting to oriented graphs with a one-page book embedding on the one-dimensional point set. For this case we present a dynamic program to compute the graph of minimum oriented dilation that runs in $O(n^8)$ time for $n$ points, and a greedy algorithm that computes a $5$-spanner in $O(n\log n)$ time.
Expanding these results finally gives us a result for two-dimensional point sets: we prove that for convex point sets the greedy triangulation results in an oriented $O(1)$-spanner.
In Proceedings of the 31st European Symposium on Algorithms (ESA 2023), volume 274 of Leibniz International Proceedings in Informatics, pages 26:1–26:16, 2023.
@inproceedings{BGKPRRW2023Oriented, author={Buchin, Kevin and Gudmundsson, Joachim and Kalb, Antonia and Popov, Aleksandr and Rehs, Carolin and van Renssen, Andr\'e and Wong, Sampson}, title={Oriented Spanners}, booktitle={Proceedings of the 31st European Symposium on Algorithms (ESA 2023)}, year={2023}, volume={274}, series={Leibniz International Proceedings in Informatics}, pages={26:1-26:16}, doi={10.4230/LIPIcs.ESA.2023.26} } -
The mutual visibility problem for fat robots
, , and .Abstract: Given a set of $n\geq 1$ unit disk robots in the Euclidean plane, we consider the fundamental problem of providing mutual visibility to them: the robots must reposition themselves to reach a configuration where they all see each other. This problem arises under obstructed visibility, where a robot cannot see another robot if there is a third robot on the straight line segment between them. This problem was solved by Sharma et al. [G. Sharma, R. Alsaedi, C. Busch, and S. Mukhopadhyay. The complete visibility problem for fat robots with lights. In Proceedings of the 19th International Conference on Distributed Computing and Networking, pages 1-4, 2018.] in the luminous robots model, where each robot is equipped with an externally visible light that can assume colors from a fixed set of colors, using 9 colors and $O(n)$ rounds. In this work, we present an algorithm that requires only 2 colors and $O(n)$ rounds. The number of colors is optimal since at least two colors are required for point robots [G.A. Di Luna, P. Flocchini, S.G. Chaudhuri, F. Poloni, N. Santoro, and G. Viglietta. Mutual visibility by luminous robots without collisions. Information and Computation, 254:392-418, 2017.].
In Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023), volume 14079 of Lecture Notes in Computer Science, pages 15–28, 2023.
@inproceedings{AGR2023Robots, author={Alsaedi, Rusul J. and Gudmundsson, Joachim and van Renssen, Andr\'e}, title={The Mutual Visibility Problem for Fat Robots}, booktitle={Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023)}, year={2023}, volume={14079}, series={Lecture Notes in Computer Science}, pages={15-28}, doi={10.1007/978-3-031-38906-1_2} } -
Generalized sweeping line spanners
and .Abstract: We present sweeping line graphs, a generalization of $\Theta$-graphs. We show that these graphs are spanners of the complete graph, as well as of the visibility graph when line segment constraints or polygonal obstacles are considered. Our proofs use general inductive arguments to make the step to the constrained setting that could apply to other spanner constructions in the unconstrained setting, removing the need to find separate proofs that they are spanning in the constrained and polygonal obstacle settings.
In Proceedings of the 28th Annual International Computing and Combinatorics Conference (COCOON 2022), volume 13595 of Lecture Notes in Computer Science, pages 406–418, 2022.
@inproceedings{LR2022Sweeping, author={Lee, Keenan and van Renssen, Andr\'e}, title={Generalized Sweeping Line Spanners}, booktitle={Proceedings of the 28th Annual International Computing and Combinatorics Conference (COCOON 2022)}, year={2022}, volume={13595}, series={Lecture Notes in Computer Science}, pages={406-418}, doi={10.1007/978-3-031-22105-7_36} } -
Covering a set of line segments with a few squares
, , , , , and .Abstract: 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.
In Proceedings of the 12th International Conference on Algorithms and Complexity (CIAC 2021), volume 12701 of Lecture Notes in Computer Science, pages 286–299, 2021.
@inproceedings{GKRSWW2021TrajectoryCovering, author={Gudmundsson, Joachim and van de Kerkhof, Mees and van Renssen, Andr\'e and Staals, Frank and Wiratma, Lionov and Wong, Sampson}, title={Covering a set of line segments with a few squares}, booktitle={Proceedings of the 12th International Conference on Algorithms and Complexity (CIAC 2021)}, year={2021}, volume={12701}, series={Lecture Notes in Computer Science}, pages={286-299}, doi={10.1007/978-3-030-75242-2_20} } -
Local routing in a tree metric 1-spanner
, , and .Abstract: Solomon and Elkin [13] constructed a shortcutting scheme for weighted trees which results in a 1-spanner for the tree metric induced by the input tree. The spanner has logarithmic lightness, logarithmic diameter, a linear number of edges and bounded degree (provided the input tree has bounded degree). This spanner has been applied in a series of papers devoted to designing bounded degree, low-diameter, low-weight $(1+\epsilon)$-spanners in Euclidean and doubling metrics. In this paper, we present a simple local routing algorithm for this tree metric spanner. The algorithm has a routing ratio of 1, is guaranteed to terminate after $O(\log n)$ hops and requires $O(\Delta \log n)$ bits of storage per vertex where $\Delta$ is the maximum degree of the tree on which the spanner is constructed.
In Proceedings of the 26th Annual International Computing and Combinatorics Conference (COCOON 2020), volume 12273 of Lecture Notes in Computer Science, pages 174–185, 2020.
@inproceedings{BGR2020TreeRouting, author={Brankovic, Milutin and Gudmundsson, Joachim and van Renssen, Andr\'e}, title={Local Routing in a Tree Metric 1-Spanner}, booktitle={Proceedings of the 26th Annual International Computing and Combinatorics Conference (COCOON 2020)}, year={2020}, volume={12273}, series={Lecture Notes in Computer Science}, pages={174-185}, doi={10.1007/978-3-030-58150-3_14} } -
Bounded-degree spanners in the presence of polygonal obstacles
and .Abstract: Let $V$ be a finite set of vertices in the plane and $S$ be a finite set of polygonal obstacles. We show how to construct a plane $2$-spanner of the visibility graph of $V$ with respect to $S$. As this graph can have unbounded degree, we modify it in three easy-to-follow steps, in order to bound the degree to $7$ at the cost of slightly increasing the spanning ratio to 6.
In Proceedings of the 26th Annual International Computing and Combinatorics Conference (COCOON 2020), volume 12273 of Lecture Notes in Computer Science, pages 40–51, 2020.
@inproceedings{RW2019BoundedDegreePolygonalObstacles, author={van Renssen, Andr\'e and Wong, Gladys}, title={Bounded-Degree Spanners in the Presence of Polygonal Obstacles}, booktitle={Proceedings of the 26th Annual International Computing and Combinatorics Conference (COCOON 2020)}, year={2020}, volume={12273}, series={Lecture Notes in Computer Science}, pages={40-51}, doi={10.1007/978-3-030-58150-3_4} } -
Kinetic geodesic Voronoi diagrams in a simple polygon
, , , and .Abstract: 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 develop a kinetic data structure (KDS) that maintains the geodesic Voronoi diagram as the sites move. To this end, we first analyze how often a single bisector, defined by two sites, or a single Voronoi center, defined by three sites, can change. For both these structures we prove that the number of such changes is at most $O(m^3)$, and that this is tight in the worst case. Moreover, we develop compact, responsive, local, and efficient kinetic data structures for both structures. Our data structures use linear space and process a worst-case optimal number of events. Our bisector KDS handles each event in $O(\log m)$ time, and our Voronoi center handles each event in $O(\log^2 m)$ time. Both structures can be extended to efficiently support updating the movement of the sites as well. Using these data structures as building blocks we obtain a compact KDS for maintaining the full geodesic Voronoi diagram.
In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics, pages 75:1–75:17, 2020.
@inproceedings{KRRS2020Kinetic, author={Korman, Matias and van Renssen, Andr\'e and Roeloffzen, Marcel and Staals, Frank}, title={Kinetic Geodesic {V}oronoi Diagrams in a Simple Polygon}, booktitle={Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, year={2020}, volume={168}, series={Leibniz International Proceedings in Informatics}, pages={75:1-75:17}, doi={10.4230/LIPIcs.ICALP.2020.75} } -
A simple dynamization of trapezoidal point location in planar subdivisions
, , , and .Abstract: We study how to dynamize the Trapezoidal Search Tree (TST) -- a well known randomized point location structure for planar subdivisions of kinetic line segments.Our approach naturally extends incremental leaf-level insertions to recursive methods and allows adaptation for the online setting. The dynamization carries over to the Trapezoidal Search DAG (TSD), which has linear size and logarithmic point location costs with high probability. On a set $S$ of non-crossing segments, each TST update performs expected $O(\log^2|S|)$ operations and each TSD update performs expected $O(\log |S|)$ operations.
We demonstrate the practicality of our method with an open-source implementation, based on the Computational Geometry Algorithms Library, and experiments on the update performance.
In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics, pages 18:1–18:18, 2020.
@inproceedings{BGRS2020PointLocation, author={Brankovic, Milutin and Grujic, Nikola and van Renssen, Andr\'e and Seybold, Martin P.}, title={A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions}, booktitle={Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, year={2020}, volume={168}, series={Leibniz International Proceedings in Informatics}, pages={18:1-18:18}, doi={10.4230/LIPIcs.ICALP.2020.18} } -
Routing in histograms
, , , , , , , and .Abstract: 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$ and $q$ in $P$ are co-visible if and only if the (axis-parallel) rectangle spanned by $p$ and $q$ completely lies in $P$. In the $r$-visibility graph $G(P)$ of $P$, we connect two vertices of $P$ with an edge if and only if they are co-visible. We consider routing with preprocessing in $G(P)$. We may preprocess $P$ to obtain a label and a routing table for each vertex of $P$. Then, we must be able to route a packet between any two vertices $s$ and $t$ of $P$, where each step may use only the label of the target node $t$, the routing table and neighborhood of the current node, and the packet header. The routing problem has been studied extensively for general graphs, and truly compact and efficient routing schemes with polylogartihmic routing tables have turned out to be impossible. Thus, special graphs classes are of interest.We present a routing scheme for double histograms that sends any data packet along a path of length at most twice the (unweighted) shortest path distance between the endpoints. The labels, routing tables, and headers need $O(\log n)$ bits. For the simple histograms, we obtain a routing scheme with optimal routing paths, $O(\log n)$-bit labels, one-bit routing tables, and no headers.
In Proceedings of the 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020), volume 12049 of Lecture Notes in Computer Science, pages 43–54, 2020.
@inproceedings{CCHKKMRRW2020Histogram, author={Chiu, Man-Kwun and Cleve, Jonas and Klost, Katharina and Korman, Matias and Mulzer, Wolfgang and van Renssen, Andr\'e and Roeloffzen, Marcel and Willert, Max}, title={Routing in Histograms}, booktitle={Proceedings of the 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020)}, year={2020}, volume={12049}, series={Lecture Notes in Computer Science}, pages={43-54}, doi={10.1007/978-3-030-39881-1_5} } -
Local routing in sparse and lightweight geometric graphs
, , , , and .Abstract: 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 [P. Bose and P. 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 $\Omega(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.
In Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC 2019), volume 149 of Leibniz International Proceedings in Informatics, pages 30:1–30:13, 2019.
@inproceedings{AGLNR2019LightRouting, author={Ashvinkumar, Vikrant and Gudmundsson, Joachim and Levcopoulos, Christos and Nilsson, Bengt J. and van Renssen, Andr\'e}, title={Local Routing in Sparse and Lightweight Geometric Graphs}, booktitle={Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC 2019)}, year={2019}, volume={149}, series={Leibniz International Proceedings in Informatics}, pages={30:1-30:13}, doi={10.4230/LIPIcs.ISAAC.2019.30} } -
Graphs with large total angular resolution
, , , , , , and .Abstract: The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawing: the angular resolution, that is the minimum angle between incident edges, and the crossing resolution, that is the minimum angle between crossing edges. We consider the total angular resolution of a graph, which is the maximum total angular resolution of a straight-line drawing of this graph. We prove that, up to a finite number of well specified exceptions of constant size, the number of edges of a graph with $n$ vertices and a total angular resolution greater than $60^{\circ}$ is bounded by $2n-6$. This bound is tight. In addition, we show that deciding whether a graph has total angular resolution at least $60^{\circ}$ is NP-hard.
In Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019), volume 11904 of Lecture Notes in Computer Science, pages 193–199, 2019.
@inproceedings{AKOPPRV2019AngularResolution, author={Aichholzer, Oswin and Korman, Matias and Okamoto, Yoshio and Parada, Irene and Perz, Daniel and van Renssen, Andr\'e and Vogtenhuber, Birgit}, title={Graphs with large total angular resolution}, booktitle={Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)}, year={2019}, volume={11904}, series={Lecture Notes in Computer Science}, pages={193-199}, doi={10.1007/978-3-030-35802-0_15} } -
Universal reconfiguration of facet-connected modular robots by pivots: The $O(1)$ musketeers
, , , , , , , , , , and .Abstract: We present the first universal reconfiguration algorithm for transforming a modular robot between any two facet-connected square-grid configurations using pivot moves. More precisely, we show that five extra “helper” modules (“musketeers”) suffice to reconfigure the remaining $n$ modules between any two given configurations. Our algorithm uses $O(n^2)$ pivot moves, which is worst-case optimal. Previous reconfiguration algorithms either require less restrictive “sliding” moves, do not preserve facet-connectivity, or for the setting we consider, could only handle a small subset of configurations defined by a local forbidden pattern. Configurations with the forbidden pattern do have disconnected reconfiguration graphs (discrete configuration spaces), and indeed we show that they can have an exponential number of connected components. But forbidding the local pattern throughout the configuration is far from necessary, as we show that just a constant number of added modules (placed to be freely reconfigurable) suffice for universal reconfigurability. We also classify three different models of natural pivot moves that preserve facet-connectivity, and show separations between these models.
In Proceedings of the 27th European Symposium on Algorithms (ESA 2019), volume 144 of Leibniz International Proceedings in Informatics, pages 3:1–3:14, 2019.
@inproceedings{AADDDFKPPRS2019Robots, author={Akitaya, Hugo A. and Arkin, Esther D. and Damian, Mirela and Demaine, Erik D. and Dujmovi\'c, Vida and Flatland, Robin and Korman, Matias and Palop, Belen and Parada, Irene and van Renssen, Andr\'e and Sacrist\'an, Vera}, title={Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: {T}he {$O(1)$} Musketeers}, booktitle={Proceedings of the 27th European Symposium on Algorithms (ESA 2019)}, year={2019}, volume={144}, series={Leibniz International Proceedings in Informatics}, pages={3:1-3:14}, doi={10.4230/LIPIcs.ESA.2019.3} } -
Rectilinear link diameter and radius in a rectilinear polygonal domain
, , , , , , , and .Abstract: 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 graph of oriented distances to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in $O (\min(n^\omega, n^2 + nh \log h + \chi^2))$ time, where $\omega<2.373$ denotes the matrix multiplication exponent and $\chi \in \Omega(n)\cap O(n^2)$ is the number of edges of the graph of oriented distances. We also provide an alternative algorithm for computing the diameter that runs in $O(n^2 \log n)$ time.
In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 2018), volume 123 of Leibniz International Proceedings in Informatics, pages 58:1–58:13, 2018.
@inproceedings{BKRV2018RectilinearLink, author={Arseneva, Elena and Chiu, Man-Kwun and Korman, Matias and Markovic, Aleksandar and Okamoto, Yoshio and Ooms, Aur\'elien and van Renssen, Andr\'e and Roeloffzen, Marcel}, title={Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain}, booktitle={Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 2018)}, year={2018}, volume={123}, series={Leibniz International Proceedings in Informatics}, pages={58:1-58:13}, doi={10.4230/LIPIcs.ISAAC.2018.58} } -
Geometry and generation of a new graph planarity game
, , , and .Abstract: We introduce a new abstract graph game, Swap Planarity, where the goal is to reach a state without edge intersections and a move consists of swapping the locations of two vertices connected by an edge. We analyze this puzzle game using concepts from graph theory and graph drawing, computational geometry, and complexity. Furthermore, we specify what good levels look like and we show how they can be generated. We also report on experiments that show how well this generation process works.
In Proceedings of the 2018 IEEE Conference on Computational Intelligence and Games (CIG 2018), pages 189–196, 2018.
@inproceedings{KKMR2018PlanarityGame, author={Kraaijer, Rutger and van Kreveld, Marc and Meulemans, Wouter and van Renssen, Andr\'e}, title={Geometry and Generation of a new Graph Planarity Game}, booktitle={Proceedings of the 2018 IEEE Conference on Computational Intelligence and Games (CIG 2018)}, year={2018}, pages={189-196}, doi={10.1109/CIG.2018.8490404} } -
Routing on the visibility graph
, , , and .Abstract: We consider the problem of routing on a network in the presence of line segment constraints (i.e., obstacles that edges in our network are not allowed to cross). Let $P$ be a set of $n$ points in the plane and let $S$ be a set of non-crossing line segments whose endpoints are in $P$. We present two deterministic 1-local $O(1)$-memory routing algorithms that are guaranteed to find a path of at most linear size between any pair of vertices of the visibility graph of $P$ with respect to a set of constraints $S$ (i.e., the algorithms never look beyond the direct neighbours of the current location and store only a constant amount of information). Contrary to all existing deterministic local routing algorithms, our routing algorithms do not route on a plane subgraph of the visibility graph.
In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017), volume 92 of Leibniz International Proceedings in Informatics, pages 18:1–18:12, 2017.
@inproceedings{BKRV2017RoutingVisibilityGraph, author={Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Verdonschot, Sander}, title={Routing on the Visibility Graph}, booktitle={Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017)}, year={2017}, volume={92}, series={Leibniz International Proceedings in Informatics}, pages={18:1-18:12}, doi={10.4230/LIPIcs.ISAAC.2017.18} } -
Routing in polygonal domains
, , , , , , , , , and .Abstract: We consider the problem of routing a data packet through the visibility graph of a polygonal domain $P$ with $n$ vertices and $h$ holes. We may preprocess $P$ to obtain a label and a routing table for each vertex. Then, we must be able to route a data packet between any two vertices $p$ and $q$ of $P$, where each step must use only the label of the target node $q$ and the routing table of the current node.For any fixed $\epsilon > 0$, we present a routing scheme that always achieves a routing path that exceeds the shortest path by a factor of at most $1 + \epsilon$. The labels have $O(\log n)$ bits, and the routing tables are of size $O((\epsilon^-1+h)\log n)$. The preprocessing time is $O(n^2\log n + hn^2+\epsilon^-1hn)$. It can be improved to $O(n^2+\epsilon^-1n)$ for simple polygons.
In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017), volume 92 of Leibniz International Proceedings in Informatics, pages 10:1–10:13, 2017.
@inproceedings{BKMRRSSVW2017Routing, author={Banyassady, Bahareh and Chiu, Man-Kwun and Korman, Matias and Mulzer, Wolfgang and van Renssen, Andr\'e and Roeloffzen, Marcel and Seiferth, Paul and Stein, Yannik and Vogtenhuber, Birgit and Willert, Max}, title={Routing in Polygonal Domains}, booktitle={Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017)}, year={2017}, volume={92}, series={Leibniz International Proceedings in Informatics}, pages={10:1-10:13}, doi={10.4230/LIPIcs.ISAAC.2017.10} } -
Fully-dynamic and kinetic conflict-free coloring of intervals with respect to points
, , , , , and .Abstract: We introduce the fully-dynamic conflict-free coloring problem for a set $S$ of intervals in$\mathbb{R}^1$ with respect to points, where the goal is to maintain a conflict-free coloring for $S$ under insertions and deletions. A coloring is conflict-free if for each point $p$ contained in some interval, $p$ is contained in an interval whose color is not shared with any other interval containing $p$. We investigate trade-offs between the number of colors used and the number of intervals that are recolored upon insertion or deletion of an interval. Our results include:- a lower bound on the number of recolorings as a function of the number of colors, which implies that with $O(1)$ recolorings per update the worst-case number of colors is $\Omega(\log n/\log\log n)$, and that any strategy using $O(1/\epsilon)$ colors needs $\Omega(\epsilon n^{\epsilon})$ recolorings;
- a coloring strategy that uses $O(\log n)$ colors at the cost of $O(\log n)$ recolorings, and another strategy that uses $O(1/\epsilon)$ colors at the cost of $O(n^{\epsilon}/\epsilon)$ recolorings;
- stronger upper and lower bounds for special cases.
In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017), volume 92 of Leibniz International Proceedings in Informatics, pages 26:1–26:13, 2017.
@inproceedings{BLMRRW2017Coloring, author={de Berg, Mark and Leijsen, Tim and Markovic, Aleksandar and van Renssen, Andr\'e and Roeloffzen, Marcel and Woeginger, Gerhard}, title={Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points}, booktitle={Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017)}, year={2017}, volume={92}, series={Leibniz International Proceedings in Informatics}, pages={26:1-26:13}, doi={10.4230/LIPIcs.ISAAC.2017.26} } -
Faster algorithms for growing prioritized disks and rectangles
, , , , , , , , and .Abstract: Motivated by map labeling, we study the problem in which we are given a collection of $n$ disks $D_1, \dots, D_n$ in the plane that grow at possibly different speeds. Whenever two disks meet, the one with the lower index disappears. This problem was introduced by Funke, Krumpe, and Storandt [IWOCA 2016]. We provide the first general subquadratic algorithm for computing the times and the order of disappearance. Our algorithm also works for other shapes (such as rectangles) and in any fixed dimension.Using quadtrees, we provide an alternative algorithm that runs in near linear time, although this second algorithm has a logarithmic dependence on either the ratio of the fastest speed to the slowest speed of disks or the spread of the disk centers (the ratio of the maximum to the minimum distance between them). Our result improves the running times of previous algorithms by Funke, Krumpe, and Storandt [IWOCA 2016], Bahrdt et al. [ALENEX 2017], and Funke and Storandt [EWCG 2017]. Finally, we give an $\Omega(n\log n)$ lower bound on the problem, showing that our quadtree algorithms are almost tight.
In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017), volume 92 of Leibniz International Proceedings in Informatics, pages 3:1–3:13, 2017.
@inproceedings{DKRR2017GrowingDisks, author={Ahn, Hee-Kap and Bae, Sang Won and Choi, Jongmin and Korman, Matias and Mulzer, Wolfgang and Oh, Eunjin and Park, Ji-won and van Renssen, Andr\'e and Vigneron, Antoine}, title={Faster Algorithms for Growing Prioritized Disks and Rectangles}, booktitle={Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017)}, year={2017}, volume={92}, series={Leibniz International Proceedings in Informatics}, pages={3:1-3:13}, doi={10.4230/LIPIcs.ISAAC.2017.3} } -
Constrained routing between non-visible vertices
, , , and .Abstract: Routing is an important problem in networks. We look at routing in the presence of line segment constraints (i.e., obstacles that our edges are not allowed to cross). Let $P$ be a set of $n$ vertices in the plane and let $S$ be a set of line segments between the vertices in $P$, with no two line segments intersecting properly. We present the first 1-local $O(1)$-memory routing algorithm on the visibility graph of $P$ with respect to a set of constraints $S$ (i.e., it never looks beyond the direct neighbours of the current location and does not need to store more than $O(1)$-information to reach the target). We also show that when routing on any triangulation $T$ of $P$ such that $S\subseteq T$, no $o(n)$-competitive routing algorithm exists when only considering the triangles intersected by the line segment from the source to the target (a technique commonly used in the unconstrained setting). Finally, we provide an $O(n)$-competitive 1-local $O(1)$-memory routing algorithm on any such $T$, which is optimal in the worst case, given the lower bound.
In Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON 2017), volume 10392 of Lecture Notes in Computer Science, pages 62–74, 2017.
@inproceedings{BKRV2017Routing, author={Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Verdonschot, Sander}, title={Constrained Routing Between Non-Visible Vertices}, booktitle={Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON 2017)}, year={2017}, volume={10392}, series={Lecture Notes in Computer Science}, pages={62-74}, doi={10.1007/978-3-319-62389-4_6} } -
Dynamic graph coloring
, , , , , , and .Abstract: 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-offs between the number of recolorings and the number of colors used. For any $d>0$, the first algorithm maintains a proper $O(\mathcal{C} d N^{1/d})$-coloring while recoloring at most $O(d)$ vertices per update, where $\mathcal{C}$ and $N$ are the maximum chromatic number and maximum number of vertices, respectively. The second algorithm reverses the trade-off, maintaining an $O(\mathcal{C} d)$-coloring with $O(d N^{1/d})$ recolorings per update. We also present a lower bound, showing that any algorithm that maintains a $c$-coloring of a $2$-colorable graph on $N$ vertices must recolor at least $\Omega(N^\frac2c(c-1))$ vertices per update, for any constant $c \geq 2$.
In Proceedings of the 15th Algorithms and Data Structures Symposium (WADS 2017), volume 10389 of Lecture Notes in Computer Science, pages 97–108, 2017.
@inproceedings{BCKLRRV2017Coloring, author={Barba, Luis and Cardinal, Jean and Korman, Matias and Langerman, Stefan and van Renssen, Andr\'e and Roeloffzen, Marcel and Verdonschot, Sander}, title={Dynamic Graph Coloring}, booktitle={Proceedings of the 15th Algorithms and Data Structures Symposium (WADS 2017)}, year={2017}, volume={10389}, series={Lecture Notes in Computer Science}, pages={97-108}, doi={10.1007/978-3-319-62127-2_9} } -
Balanced line separators of unit disk graphs
, , , , , , , , and .Abstract: 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 halfplanes determined by $\ell$ contains at most $2n/3$ unit disks from the set, where $m$ is the number of intersecting pairs of disks. We also show that an axis-parallel line intersecting $O(\sqrt{m+n})$ disks exists, but each halfplane may contain up to $4n/5$ disks. We give an almost tight lower bound (up to sublogarithmic factors) for our approach, and also show that no line-separator of sublinear size in $n$ exists when we look at disks of arbitrary radii, even when $m=0$. Proofs are constructive and suggest simple algorithms that run in linear time. Experimental evaluation has also been conducted, which shows that for random instances our method outperforms the method by Fox and Pach (whose separator has size $O(\sqrt{m})$).
In Proceedings of the 15th Algorithms and Data Structures Symposium (WADS 2017), volume 10389 of Lecture Notes in Computer Science, pages 241–252, 2017.
@inproceedings{CCKKORRSS2017LineSeparator, author={Carmi, Paz and Chiu, Man-Kwun and Katz, Matya and Korman, Matias and Okamoto, Yoshio and van Renssen, Andr\'e and Roeloffzen, Marcel and Shiitada, Taichi and Smorodinsky, Shakhar}, title={Balanced Line Separators of Unit Disk Graphs}, booktitle={Proceedings of the 15th Algorithms and Data Structures Symposium (WADS 2017)}, year={2017}, volume={10389}, series={Lecture Notes in Computer Science}, pages={241-252}, doi={10.1007/978-3-319-62127-2_21} } -
Snipperclips: Cutting tools into desired polygons using themselves
, , , and .Abstract: 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 computational problem of, given a target shape represented by a polygonal domain of $n$ vertices, is it possible to create it as one of the tools’ shape via a sequence of snip operations? If so, how many snip operations are required? We show that a polynomial number of snips suffice for two different variants of the problem.
In Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017), pages 56–61, 2017.
@inproceedings{DKRR2017Snipperclips, author={Demaine, Erik D. and Korman, Matias and van Renssen, Andr\'e and Roeloffzen, Marcel}, title={Snipperclips: {C}utting Tools into Desired Polygons using Themselves}, booktitle={Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017)}, year={2017}, pages={56-61} } -
Improved time-space trade-offs for computing Voronoi diagrams
, , , , , , and .Abstract: Let $P$ be a planar $n$-point set in general position. For $k \in {1, \dots, n-1}$, the Voronoi diagram of order $k$ is obtained by subdividing the plane into regions such that points in the same cell have the same set of nearest $k$ neighbors in $P$. The (nearest point) Voronoi diagram (NVD) and the farthest point Voronoi diagram (FVD) are the particular cases of $k=1$ and $k=n-1$, respectively. It is known that the family of all higher-order Voronoi diagrams of order $1$ to $K$ for $P$ can be computed in total time $O(nK^2+ n\log n)$ using $O(K^2(n-K))$ space. Also NVD and FVD can be computed in $O(n\log n)$ time using $O(n)$ space.For $s \in {1, \ldots, n}$, an $s$-workspace algorithm has random access to a read-only array with the sites of $P$ in arbitrary order. Additionally, the algorithm may use $O(s)$ words of $\Theta(\log n)$ bits each for reading and writing intermediate data. The output can be written only once and cannot be accessed afterwards.
We describe a deterministic $s$-workspace algorithm for computing an NVD and also an FVD for $P$ that runs in $O((n^2/s)\log s)$ time. Moreover, we generalize our s-workspace algorithm for computing the family of all higher-order Voronoi diagrams of $P$ up to order $K\in O(\sqrt{s})$ in total time $O\bigl(\frac{n^2 K^6}{s}\log^{1+\epsilon} K\cdot (\log s /\log K)^{O(1)}\bigr)$, for any fixed $\epsilon > 0$. Previously, for Voronoi diagrams, the only known s-workspace algorithm was to find an NVD for $P$ in expected time $O((n^2/s) \log s + n \log s \log^*s)$. Unlike the previous algorithm, our new method is very simple and does not rely on advanced data structures or random sampling techniques.
In Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS 2017), volume 66 of Leibniz International Proceedings in Informatics, pages 9:1–9:14, 2017.
@inproceedings{BKRV2017Voronoi, author={Banyassady, Bahareh and Korman, Matias and Mulzer, Wolfgang and van Renssen, Andr\'e and Roeloffzen, Marcel and Seiferth, Paul and Stein, Yannik}, title={Improved Time-Space Trade-offs for Computing {V}oronoi Diagrams}, booktitle={Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, year={2017}, volume={66}, series={Leibniz International Proceedings in Informatics}, pages={9:1--9:14}, doi={10.4230/LIPIcs.STACS.2017.9} } -
Packing short plane spanning trees in complete geometric graphs
, , , , , , , and .Abstract: Given a set of points in the plane, we want to establish a connection network between these points that consist of several disjoint layers. Motivated from sensor networks, we want that each layer is spanning and plane, and that no edge is very long (when compared to the minimum length needed to obtain a spanning graph). We consider two different approaches: first we show an almost optimal centralized approach to extract two layers. Then we show how a constant factor approximation for a distributed model in which each point can compute its adjacencies using only local information.
In Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016), volume 64 of Leibniz International Proceedings in Informatics, pages 9:1–9:12, 2016.
@inproceedings{AHKPRRRV2016SpanningTrees, author={Aichholzer, Oswin and Hackl, Thomas and Korman, Matias and Pilz, Alexander and Rote, Gunter and van Renssen, Andr\'e and Roeloffzen, Marcel and Vogtenhuber, Birgit}, title={Packing Short Plane Spanning Trees in Complete Geometric Graphs}, booktitle={Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016)}, year={2016}, volume={64}, series={Leibniz International Proceedings in Informatics}, pages={9:1--9:12}, doi={10.4230/LIPIcs.ISAAC.2016.9} } -
Symmetric assembly puzzles are hard, beyond a few pieces
, , , , , , , , and .Abstract: We study the complexity of symmetric assembly puzzles: given a collection of simple polygons, can we translate, rotate, and possibly flip them so that their interior-disjoint union is line symmetric? On the negative side, we show that the problem is strongly NP-complete even if the pieces are all convex quadrilaterals. On the positive side, we show that the problem can be solved in polynomial time if the number of pieces is a fixed constant.
In Proceedings of the Proceedings-version of the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG^2 2015), volume 9943 of Lecture Notes in Computer Science, pages 180–192, 2016.
@inproceedings{DKKMORRUU2016PuzzleProc, author={Demaine, Erik D. and Korman, Matias and Ku, Jason S. and Mitchell, Joseph and Otachi, Yota and van Renssen, Andr\'e and Roeloffzen, Marcel and Uehara, Ryuhei and Uno, Yushi}, title={Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces}, booktitle={Proceedings of the Proceedings-version of the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG^2 2015)}, year={2016}, volume={9943}, series={Lecture Notes in Computer Science}, pages={180--192}, doi={10.1007/978-3-319-48532-4_16} } -
Constrained generalized Delaunay graphs are plane spanners
, , and .Abstract: We look at generalized Delaunay graphs in the constrained setting by introducing line segments which the edges of the graph are not allowed to cross. Given an arbitrary convex shape $C$, a constrained Delaunay graph is constructed by adding an edge between two vertices $p$ and $q$ if and only if there exists a homothet of $C$ with $p$ and $q$ on its boundary that does not contain any other vertices visible to $p$ and $q$. We show that, regardless of the convex shape $C$ used to construct the constrained Delaunay graph, there exists a constant $t$ (that depends on $C$) such that it is a plane $t$-spanner of the visibility graph.
In Proceedings of the Computational Intelligence in Information Systems (CIIS 2016), volume 532 of Advances in Intelligent Systems and Computing, pages 281–293, 2016.
@inproceedings{BCR2016GeneralizedDelaunay, author={Bose, Prosenjit and De Carufel, Jean-Lou and van Renssen, Andr\'e}, title={Constrained Generalized {D}elaunay Graphs Are Plane Spanners}, booktitle={Proceedings of the Computational Intelligence in Information Systems (CIIS 2016)}, year={2016}, volume={532}, series={Advances in Intelligent Systems and Computing}, pages={281--293}, doi={10.1007/978-3-319-48517-1_25} } -
On interference among moving sensors and related problems
, , , , , and .Abstract: We show that for any set of $n$ moving points in $\mathbb{R}^d$ and any parameter $2 \le k \le n$, one can select a fixed non-empty subset of the points of size $O(k \log k)$, such that the Voronoi diagram of this subset is “balanced” at any given time (i.e., it contains $O(n/k)$ points per cell). We also show that the bound $O(k \log k)$ is near optimal even for the one dimensional case in which points move linearly. As an application, we show that one can assign communication radii to the sensors of a network of $n$ moving sensors so that at any given time, their interference is $O(\sqrt{n\log n})$. This is optimal up to an $O(\sqrt{\log n})$ factor.
In Proceedings of the 24th European Symposium on Algorithms (ESA 2016), volume 57 of Leibniz International Proceedings in Informatics, pages 34:1–34:11, 2016.
@inproceedings{CKKRRS2016Interference, author={De Carufel, Jean-Lou and Katz, Matya and Korman, Matias and van Renssen, Andr\'e and Roeloffzen, Marcel and Smorodinsky, Shakhar}, title={On interference among moving sensors and related problems}, booktitle={Proceedings of the 24th European Symposium on Algorithms (ESA 2016)}, year={2016}, volume={57}, series={Leibniz International Proceedings in Informatics}, pages={34:1--34:11}, doi={10.4230/LIPIcs.ESA.2016.34} } -
Time-space trade-offs for triangulating a simple polygon
, , , , and .Abstract: An $s$-workspace algorithm is an algorithm that has read-only access to the values of the input and only uses $O(s)$ additional words of space. We give a randomized $s$-workspace algorithm for triangulating a simple polygon $P$ of $n$ vertices, for any $s\in \Omega(\log n)\cap O(n)$. The algorithm runs in $O(n^2/s)$ expected time. We also extend the approach to compute other similar structures such as the shortest-path map (or tree) of any point $p\in P$, or how to partition $P$ using only diagonals of the polygon so that the resulting sub-polygons have $\Theta(s)$ vertices each.
In Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), volume 53 of Leibniz International Proceedings in Informatics, pages 30:1–30:12, 2016.
@inproceedings{AKPRR2016Triangulating, author={Aronov, Boris and Korman, Matias and Pratt, Simon and van Renssen, Andr\'e and Roeloffzen, Marcel}, title={Time-Space Trade-offs for Triangulating a Simple Polygon}, booktitle={Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, year={2016}, volume={53}, series={Leibniz International Proceedings in Informatics}, pages={30:1--30:12}, doi={10.4230/LIPIcs.SWAT.2016.30} } -
Hanabi is NP-complete, even for cheaters who look at their cards
, , , , , , , and .Abstract: This paper studies a cooperative card game called Hanabi from an algorithmic combinatorial game theory viewpoint. The aim of the game is to play cards from $1$ to $n$ in increasing order (this has to be done independently in $c$ different colors). Cards are drawn from a deck one by one. Drawn cards are either immediately played, discarded or stored for future use (overall each player can store up to $h$ cards).We introduce a simplified mathematical model of a single-player version of the game, and show several complexity results: the game is intractable in a general setting, but becomes tractable (and even linear) in some interesting restricted cases (i.e., for small values of $h$ and $c$).
In Proceedings of the 8th International Conference on Fun with Algorithms (FUN 2016), volume 49 of Leibniz International Proceedings in Informatics, pages 4:1–4:17, 2016.
@inproceedings{BCDKMRRU2016Hanabi, author={Baffier, Jean-Francois and Chiu, Man-Kwun and Diez, Yago and Korman, Matias and Mitsou, Valia and van Renssen, Andr\'e and Roeloffzen, Marcel and Uno, Yushi}, title={Hanabi is {NP}-complete, Even for Cheaters who Look at Their Cards}, booktitle={Proceedings of the 8th International Conference on Fun with Algorithms (FUN 2016)}, year={2016}, volume={49}, series={Leibniz International Proceedings in Informatics}, pages={4:1--4:17}, doi={10.4230/LIPIcs.FUN.2016.4} } -
Competitive local routing with constraints
, , , and .Abstract: Let $P$ be a set of $n$ vertices in the plane and $S$ a set of non-crossing line segments between vertices in $P$, called constraints. Two vertices are visible if the straight line segment connecting them does not properly intersect any constraints. The constrained $\theta_m$-graph is constructed by partitioning the plane around each vertex into $m$ disjoint cones with aperture $\theta = 2 \pi/m$, and adding an edge to the ‘closest’ visible vertex in each cone. We consider how to route on the constrained $\theta_6$-graph. We first show that no deterministic 1-local routing algorithm is $o(\sqrt{n})$-competitive on all pairs of vertices of the constrained $\theta_6$-graph. After that, we show how to route between any two visible vertices using only 1-local information, while guaranteeing that the returned path has length at most 2 times the Euclidean distance between the source and destination. To the best of our knowledge, this is the first local routing algorithm in the constrained setting with guarantees on the path length.
In Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC 2015), volume 9472 of Lecture Notes in Computer Science, pages 23–34, 2015.
@inproceedings{BFRV2015Routing, author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander}, title={Competitive Local Routing with Constraints}, booktitle={Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC 2015)}, year={2015}, volume={9472}, series={Lecture Notes in Computer Science}, pages={23-34}, doi={10.1007/978-3-662-48971-0_3} } -
Upper and lower bounds for online routing on Delaunay triangulations
, , , , and .Abstract: Consider a weighted graph $G$ whose vertices are points in the plane and edges are line segments between pairs of points whose weight is the Euclidean distance between its endpoints. A routing algorithm on $G$ sends a message from any vertex $s$ to any vertex $t$ in $G$. The algorithm has a competitive ratio of $c$ if the length of the path taken by the message is at most $c$ times the length of the shortest path from $s$ to $t$ in $G$. It has a routing ratio of $c$ if the length of the path is at most $c$ times the Euclidean distance from $s$ to $t$. The algorithm is online if it makes forwarding decisions based on (1) the $k$-neighborhood in $G$ of the message’s current position (for constant $k>0$) and (2) limited information stored in the message header.We present an online routing algorithm on the Delaunay triangulation with routing ratio less than $5.90$, improving the best known routing ratio of $15.48$. Our algorithm makes forwarding decisions based on the $1$-neighborhood of the current position of the message and the positions of the message source and destination only.
We present a lower bound of $5.7282$ on the routing ratio of our algorithm, so the $5.90$ upper bound is close to best possible. We also show that the routing (resp., competitive) ratio of any deterministic $k$-local algorithm is at least $1.70$ (resp., $1.23$) for the Delaunay triangulation and $2.70$ (resp. $1.23$) for the $L_1$-Delaunay triangulation. In the case of the $L_1$-Delaunay triangulation, this implies that even though there always exists a path between $s$ and $t$ whose length is at most $2.61|[st]|$, it is not always possible to route a message along a path of length less than $2.70|[st]|$ using only local information.
In Proceedings of the 23rd European Symposium on Algorithms (ESA 2015), volume 9294 of Lecture Notes in Computer Science, pages 203–214, 2015.
@inproceedings{BBCPR2015Delaunay, author={Bonichon, Nicolas and Bose, Prosenjit and De Carufel, Jean-Lou and Perkovi\'c, Ljubomir and van Renssen, Andr\'e}, title={Upper and Lower Bounds for Online Routing on {D}elaunay Triangulations}, booktitle={Proceedings of the 23rd European Symposium on Algorithms (ESA 2015)}, year={2015}, volume={9294}, series={Lecture Notes in Computer Science}, pages={203-214}, doi={10.1007/978-3-662-48350-3_18} } -
Constrained empty-rectangle Delaunay graphs
, , and .Abstract: Given an arbitrary convex shape $C$, a set $P$ of points in the plane and a set $S$ of line segments whose endpoints are in $P$, a constrained generalized Delaunay graph of $P$ with respect to $C$ denoted $CDG_C(P)$ is constructed by adding an edge between two points $p$ and $q$ if and only if there exists a homothet of $C$ with $p$ and $q$ on its boundary and no point of $P$ in the interior visible to both $p$ and $q$. We study the case where the empty convex shape is an arbitrary rectangle and show that it has spanning ratio at most $\sqrt{2} \cdot \left( 2 l/s + 1 \right)$, where $l$ and $s$ are the length of the long and short side of the rectangle.
In Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG 2015), pages 57–62, 2015.
@inproceedings{BCR2015Rectangles, author={Bose, Prosenjit and De Carufel, Jean-Lou and van Renssen, Andr\'e}, title={Constrained Empty-Rectangle {D}elaunay Graphs}, booktitle={Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG 2015)}, year={2015}, pages={57-62} } -
Time-space trade-offs for triangulations and Voronoi diagrams
, , , , , and .Abstract: Let $S$ be a planar $n$-point set. A triangulation for $S$ is a maximal plane straight-line graph with vertex set $S$. The Voronoi diagram for $S$ is the subdivision of the plane into cells such that each cell has the same nearest neighbors in $S$. Classically, both structures can be computed in $O(n \log n)$ time and $O(n)$ space. We study the situation when the available workspace is limited: given a parameter $s \in {1, \dots, n}$, an $s$-workspace algorithm has read-only access to an input array with the points from $S$ in arbitrary order, and it may use only $O(s)$ additional words of $\Theta(\log n)$ bits for reading and writing intermediate data. The output should then be written to a write-only structure. We describe a deterministic $s$-workspace algorithm for computing a triangulation of $S$ in time $O(n^2/s + n \log n \log s )$ and a randomized $s$-workspace algorithm for finding the Voronoi diagram of $S$ in expected time $O((n^2/s) \log s + n \log s \log^*s)$.
In Proceedings of the 14th Algorithms and Data Structures Symposium (WADS 2015), volume 9214 of Lecture Notes in Computer Science, pages 482–492, 2015.
@inproceedings{KMRRSS2015VoronoiConference, author={Korman, Matias and Mulzer, Wolfgang and van Renssen, Andr\'e and Roeloffzen, Marcel and Seiferth, Paul and Stein, Yannik}, title={Time-Space Trade-offs for Triangulations and {V}oronoi Diagrams}, booktitle={Proceedings of the 14th Algorithms and Data Structures Symposium (WADS 2015)}, year={2015}, volume={9214}, series={Lecture Notes in Computer Science}, pages={482-492}, doi={10.1007/978-3-319-21840-3_40} } -
The price of order
, , and .Abstract: A $\theta$-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $\theta = 2 \pi/m$. An ordered $\theta$-graph is constructed by inserting the vertices one by one and connecting each vertex to the closest previously-inserted vertex in each cone. We present tight bounds on the spanning ratio of a large family of ordered $\theta$-graphs. We also provide lower bounds for all ordered $\theta$-graphs. For ordered $\theta$-graphs with $4k + 2$ and $4k + 5$ cones ($k \geq 1$) these lower bounds are strictly greater than the worst case spanning ratios of their unordered counterparts. These are the first results showing that ordered $\theta$-graphs have worse spanning ratios than unordered $\theta$-graphs. Finally, we show that, unlike their unordered counterparts, the ordered $\theta$-graphs with 4, 5, and 6 cones are not spanners.
In Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014), volume 8889 of Lecture Notes in Computer Science, pages 313–325, 2014.
@inproceedings{BMR2014Order, author={Bose, Prosenjit and Morin, Pat and van Renssen, Andr\'e}, title={The Price of Order}, booktitle={Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014)}, year={2014}, volume={8889}, series={Lecture Notes in Computer Science}, pages={313--325}, doi={10.1007/978-3-319-13075-0_25} } -
Continuous Yao graphs
, , , , , , , and .Abstract: In this paper, we introduce a variation of the well-studied Yao graphs. Given a set of points $S\subset \mathbb{R}^2$ and an angle $0 < \theta \leq 2\pi$, we define the continuous Yao graph $cY(\theta)$ with vertex set $S$ and angle $\theta$ as follows. For each $p,q\in S$, we add an edge from $p$ to $q$ in $cY(\theta)$ if there exists a cone with apex $p$ and aperture $\theta$ such that $q$ is the closest point to $p$ inside this cone.We study the spanning ratio of $cY(\theta)$ for different values of $\theta$. Using a new algebraic technique, we show that $cY(\theta)$ is a spanner when $\theta \leq 2\pi /3$. We believe that this technique may be of independent interest. We also show that $cY(\pi)$ is not a spanner, and that $cY(\theta)$ may be disconnected for $\theta > \pi$.
In Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG 2014), pages 100–106, 2014.
@inproceedings{BBCDFRTV2014Continuous, author={Barba, Luis and Bose, Prosenjit and De Carufel, Jean-Lou and Damian, Mirela and Fagerberg, Rolf and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander}, title={Continuous {Y}ao Graphs}, booktitle={Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG 2014)}, year={2014}, pages={100--106} } -
On the spanning ratio of constrained Yao-graphs
.Abstract: We present upper bounds on the spanning ratio of constrained Yao-graphs with at least 7 cones. Given a set of points in the plane, a Yao-graph partitions the plane around each vertex into $k$ disjoint cones, each having aperture $\theta = 2 \pi/k$, and adds an edge to the closest vertex in each cone. Constrained Yao-graphs have the additional property that no edge properly intersects any of the given line segment constraints. We show that constrained Yao-graphs with an even number of cones ($k \geq 8$) have spanning ratio at most $1 / \left( 1 - 2 \sin (\theta/2) \right)$ and constrained Yao-graphs with an odd number of cones ($k \geq 7$) have spanning ratio at most $1 / \left( 1 - 2 \sin (3\theta/8) \right)$. These bounds match the current upper bounds in the unconstrained setting.
In Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG 2014), pages 239–243, 2014.
@inproceedings{R2014Yao, author={van Renssen, Andr\'e}, title={On the Spanning Ratio of Constrained {Y}ao-Graphs}, booktitle={Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG 2014)}, year={2014}, pages={239--243} } -
New and improved spanning ratios for Yao graphs
, , , , , , , , , and .Abstract: For a set of points in the plane and a fixed integer $k > 0$, the Yao graph $Y_k$ partitions the space around each point into $k$ equiangular cones of angle $\theta=2\pi/k$, and connects each point to a nearest neighbor in each cone. It is known for all Yao graphs, with the sole exception of $Y_5$, whether or not they are geometric spanners. In this paper we close this gap by showing that for odd $k \geq 5$, the spanning ratio of $Y_k$ is at most $1/(1-2\sin(3\theta/8))$, which gives the first constant upper bound for $Y_5$, and is an improvement over the previous bound of $1/(1-2\sin(\theta/2))$ for odd $k \geq 7$. We further reduce the upper bound on the spanning ratio for $Y_5$ from $10.9$ to $2+\sqrt{3} \approx 3.74$, which falls slightly below the lower bound of $3.79$ established for the spanning ratio of $\Theta_5$ ($\Theta$-graphs differ from Yao graphs only in the way they select the closest neighbor in each cone). This is the first such separation between a Yao and $\Theta$-graph with the same number of cones. We also give a lower bound of $2.87$ on the spanning ratio of $Y_5$. Finally, we revisit the $Y_6$ graph, which plays a particularly important role as the transition between the graphs ($k > 6$) for which simple inductive proofs are known, and the graphs ($k \le 6$) whose best spanning ratios have been established by complex arguments. Here we reduce the known spanning ratio of $Y_6$ from $17.6$ to $5.8$, getting closer to the spanning ratio of 2 established for $\Theta_6$.
In Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG 2014), pages 30–39, 2014.
@inproceedings{BBDFKORTVX2014Yao, author={Barba, Luis and Bose, Prosenjit and Damian, Mirela and Fagerberg, Rolf and Keng, Wah Loon and O'Rourke, Joseph and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander and Xia, Ge}, title={New and Improved Spanning Ratios for {Y}ao Graphs}, booktitle={Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG 2014)}, year={2014}, pages={30--39} } -
Upper bounds on the spanning ratio of constrained theta-graphs
and .Abstract: We present tight upper and lower bounds on the spanning ratio of a large family of constrained $\theta$-graphs. We show that constrained $\theta$-graphs with $4k + 2$ ($k \geq 1$ and integer) cones have a tight spanning ratio of $1 + 2 \sin(\theta/2)$, where $\theta$ is $2 \pi / (4k + 2)$. We also present improved upper bounds on the spanning ratio of the other families of constrained $\theta$-graphs.
In Proceedings of the 11th Latin American Symposium on Theoretical Informatics (LATIN 2014), volume 8392 of Lecture Notes in Computer Science, pages 108–119, 2014.
@inproceedings{BR2014ConstrainedTheta, author={Bose, Prosenjit and van Renssen, Andr\'e}, title={Upper Bounds on the Spanning Ratio of Constrained Theta-Graphs}, booktitle={Proceedings of the 11th Latin American Symposium on Theoretical Informatics (LATIN 2014)}, year={2014}, volume={8392}, series={Lecture Notes in Computer Science}, pages={108--119}, doi={10.1007/978-3-642-54423-1_10} } -
On the stretch factor of the theta-4 graph
, , , , and .Abstract: In this paper we show that the $\theta$-graph with 4 cones has constant stretch factor, i.e., there is a path between any pair of vertices in this graph whose length is at most a constant times the Euclidean distance between that pair of vertices. This is the last $\theta$-graph for which it was not known whether its stretch factor was bounded.
In Proceedings of the 13th Algorithms and Data Structures Symposium (WADS 2013), volume 8037 of Lecture Notes in Computer Science, pages 109–120, 2013.
@inproceedings{BBCRV2013Theta4, author={Barba, Luis and Bose, Prosenjit and De Carufel, Jean-Lou and van Renssen, Andr\'e and Verdonschot, Sander}, title={On the stretch factor of the Theta-4 graph}, booktitle={Proceedings of the 13th Algorithms and Data Structures Symposium (WADS 2013)}, year={2013}, volume={8037}, series={Lecture Notes in Computer Science}, pages={109--120}, doi={10.1007/978-3-642-40104-6_10} } -
On the spanning ratio of theta-graphs
, , and .Abstract: We present improved upper bounds on the spanning ratio of a large family of $\theta$-graphs. A $\theta$-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $\theta = 2 \pi/m$. We show that for any integer $k \geq 1$, $\theta$-graphs with $4k + 4$ cones have spanning ratio at most $1 + 2 \sin(\theta/2) / (\cos(\theta/2) - \sin(\theta/2))$. We also show that $\theta$-graphs with $4k + 3$ and $4k + 5$ cones have spanning ratio at most $\cos (\theta/4) / (\cos (\theta/2) - \sin (3\theta/4))$. This is a significant improvement on all families of $\theta$-graphs for which exact bounds are not known. For example, the spanning ratio of the $\theta$-graph with 7 cones is decreased from at most 7.5625 to at most 3.5132. We also improve the upper bounds on the competitiveness of the $\theta$-routing algorithm for these graphs to $1 + 2 \sin(\theta/2) / (\cos(\theta/2) - \sin(\theta/2))$ on $\theta$-graphs with $4k + 4$ cones and to $1 + 2 \sin(\theta/2) \cdot \cos (\theta/4) / (\cos (\theta/2) - \sin (3\theta/4))$ on $\theta$-graphs with $4k + 3$ and $4k + 5$ cones. For example, the routing ratio of the $\theta$-graph with 7 cones is decreased from at most 7.5625 to at most 4.0490.
In Proceedings of the 13th Algorithms and Data Structures Symposium (WADS 2013), volume 8037 of Lecture Notes in Computer Science, pages 182–194, 2013.
@inproceedings{BRV2013Theta4k345, author={Bose, Prosenjit and van Renssen, Andr\'e and Verdonschot, Sander}, title={On the Spanning Ratio of Theta-Graphs}, booktitle={Proceedings of the 13th Algorithms and Data Structures Symposium (WADS 2013)}, year={2013}, volume={8037}, series={Lecture Notes in Computer Science}, pages={182--194}, doi={10.1007/978-3-642-40104-6_16} } -
Theta-3 is connected
, , , , , , , and .Abstract: In this paper, we show that the $\theta$-graph with three cones is connected. We also provide an alternative proof of the connectivity of the Yao-graph with three cones.
In Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), pages 205–210, 2013.
@inproceedings{ABBBKRTV2013Theta3, author={Aichholzer, Oswin and Bae, Sang Won and Barba, Luis and Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander}, title={Theta-3 is connected}, booktitle={Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013)}, year={2013}, pages={205--210} } -
The $\theta_5$-graph is a spanner
, , , and .Abstract: Given a set of points in the plane, we show that the $\theta$-graph with 5 cones is a geometric spanner with spanning ratio at most $\sqrt{50 + 22 \sqrt{5}} \approx 9.960$. This is the first constant upper bound on the spanning ratio of this graph. The upper bound uses a constructive argument, giving a, possibly self-intersecting, path between any two vertices, whose length is at most $\sqrt{50 + 22 \sqrt{5}}$ times the Euclidean distance between the vertices. We also give a lower bound on the spanning ratio of $\frac{1}{2}(11\sqrt{5} -17) \approx 3.798$.
In Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013), volume 8165 of Lecture Notes in Computer Science, pages 100–114, 2013.
@inproceedings{BMRV2013Theta5, author={Bose, Prosenjit and Morin, Pat and van Renssen, Andr\'e and Verdonschot, Sander}, title={The $\theta_5$-graph is a spanner}, booktitle={Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013)}, year={2013}, volume={8165}, series={Lecture Notes in Computer Science}, pages={100--114}, doi={10.1007/978-3-642-45043-3_10} } -
Optimal bounds on theta-graphs: More is not always better
, , , , and .Abstract: We present tight upper and lower bounds on the spanning ratio of a large family of $\theta$-graphs. We show that $\theta$-graphs with $4k + 2$ cones ($k \geq 1$ and integer) have a spanning ratio of $1 + 2 \sin(\theta/2)$, where $\theta$ is $2 \pi / (4k + 2)$. We also show that $\theta$-graphs with $4k + 4$ cones have spanning ratio at least $1 + 2 \tan(\theta/2) + 2 \tan^2(\theta/2)$, where $\theta$ is $2 \pi / (4k + 4)$. This is somewhat surprising since, for equal values of $k$, the spanning ratio of $\theta$-graphs with $4k + 4$ cones is greater than that of $\theta$-graphs with $4k + 2$ cones, showing that increasing the number of cones can make the spanning ratio worse.
In Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012), pages 305–310, 2012.
@inproceedings{BCMRV2012OptimalBounds, author={Bose, Prosenjit and De Carufel, Jean-Lou and Morin, Pat and van Renssen, Andr\'e and Verdonschot, Sander}, title={Optimal Bounds on Theta-Graphs: {M}ore is not Always Better}, booktitle={Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012)}, year={2012}, pages={305--310} } -
Competitive routing on a bounded-degree plane spanner
, , , and .Abstract: We show that it is possible to route locally and competitively on two bounded-degree plane 6-spanners, one with maximum degree 12 and the other with maximum degree 9. Both spanners are subgraphs of the empty equilateral triangle Delaunay triangulation. First, in a weak routing model where the only information stored at each vertex is its neighbourhood, we show how to find a path between any two vertices of a 6-spanner of maximum degree 12, such that the path has length at most $95/\sqrt{3}$ times the straight-line distance between the vertices. In a slightly stronger model, where in addition to the neighbourhood of each vertex, we store $O(1)$ additional information, we show how to find a path that has length at most $15/\sqrt{3}$ times the Euclidean distance both in a 6-spanner of maximum degree 12 and a 6-spanner of maximum degree 9.
In Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012), pages 299–304, 2012.
@inproceedings{BFRV2012BoundedRouting, author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander}, title={Competitive Routing on a Bounded-Degree Plane Spanner}, booktitle={Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012)}, year={2012}, pages={299--304} } -
On plane constrained bounded-degree spanners
, , , and .Abstract: Let $P$ be a set of points in the plane and $S$ a set of non-crossing line segments with endpoints in $P$. The visibility graph of $P$ with respect to $S$, denoted $Vis(P,S)$, has vertex set $P$ and an edge for each pair of vertices $u,v$ in $P$ for which no line segment of $S$ properly intersects $uv$. We show that the constrained half-$\theta_6$-graph (which is identical to the constrained Delaunay graph whose empty visible region is an equilateral triangle) is a plane 2-spanner of $Vis(P,S)$. We then show how to construct a plane 6-spanner of $Vis(P,S)$ with maximum degree $6+c$, where $c$ is the maximum number of segments adjacent to a vertex.
In Proceedings of the 10th Latin American Symposium on Theoretical Informatics (LATIN 2012), volume 7256 of Lecture Notes in Computer Science, pages 85–96, 2012.
@inproceedings{BFRV2012ConstrainedBounded, author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander}, title={On Plane Constrained Bounded-Degree Spanners}, booktitle={Proceedings of the 10th Latin American Symposium on Theoretical Informatics (LATIN 2012)}, year={2012}, volume={7256}, series={Lecture Notes in Computer Science}, pages={85--96}, doi={10.1007/978-3-642-29344-3_8} } -
Competitive routing in the half-$\theta_6$-graph
, , , and .Abstract: We present a deterministic local routing scheme that is guaranteed to find a path between any pair of vertices in a half-$\theta_6$-graph whose length is at most $5/\sqrt{3}$ times the Euclidean distance between the pair of vertices. The half-$\theta_6$-graph is identical to the Delaunay triangulation where the empty region is an equilateral triangle. Moreover, we show that no local routing scheme can achieve a better competitive spanning ratio thereby implying that our routing scheme is optimal. This is somewhat surprising because the spanning ratio of the half-$\theta_6$-graph is 2. Since every triangulation can be embedded in the plane as a half-$\theta_6$-graph using $O(\log n)$ bits per vertex coordinate via Schnyder’s embedding scheme (SODA 1990), our result provides a competitive local routing scheme for every such embedded triangulation.
In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pages 1319–1328, 2012.
@inproceedings{BFRV2012Routing, author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander}, title={Competitive Routing in the Half-$\theta_6$-Graph}, booktitle={Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)}, year={2012}, pages={1319--1328} } -
Making triangulations 4-connected using flips
, , , , and .Abstract: We show that any triangulation on $n$ vertices can be transformed into a 4-connected one using at most $\lfloor(3n - 6)/5\rfloor$ edge flips. We also give an example of a triangulation that requires $\lceil(3n - 10)/5\rceil$ flips to be made 4-connected, showing that our bound is tight. Our result implies a new upper bound on the diameter of the flip graph of $5.2 n - 24.4$, improving on the bound of $6n -30$ by Mori et al.
In Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), pages 241–247, 2011.
@inproceedings{BJRSV2011Triangulations, author={Bose, Prosenjit and Jansens, Dana and van Renssen, Andr\'e and Saumell, Maria and Verdonschot, Sander}, title={Making triangulations 4-connected using flips}, booktitle={Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011)}, year={2011}, pages={241--247} } -
The 2$\times$2 simple packing problem
and .Abstract: We significantly extend the class of polygons for which the 2$\times$2 Simple Packing Problem can be solved in polynomial time.
In Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), pages 387–392, 2011.
@inproceedings{RS2011Packing, author={van Renssen, Andr\'e and Speckmann, Bettina}, title={The 2$\times$2 Simple Packing Problem}, booktitle={Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011)}, year={2011}, pages={387--392} } -
Area-preserving subdivision schematization
, , and .Abstract: We describe an area-preserving subdivision schematization algorithm: the area of each region in the input equals the area of the corresponding region in the output. Our schematization is axis-aligned, the final output is a rectilinear subdivision. We first describe how to convert a given subdivision into an area-equivalent rectilinear subdivision. Then we define two area-preserving contraction operations and prove that at least one of these operations can always be applied to any given simple rectilinear polygon. We extend this approach to subdivisions and showcase experimental results. Finally, we give examples for standard distance metrics (symmetric difference, Hausdorff- and Fréchet-distance) that show that better schematizations might result in worse shapes.
In Proceedings of the 6th International Conference on Geographic Information Science (GIScience 2010), volume 6292 of Lecture Notes in Computer Science, pages 160–174, 2010.
@inproceedings{MRS2010Schematization, author={Meulemans, Wouter and van Renssen, Andr\'e and Speckmann, Bettina}, title={Area-Preserving Subdivision Schematization}, booktitle={Proceedings of the 6th International Conference on Geographic Information Science (GIScience 2010)}, year={2010}, volume={6292}, series={Lecture Notes in Computer Science}, pages={160--174}, doi={10.1007/978-3-642-15300-6_12} }
Abstracts
Extended abstracts that I presented are marked with .
(Icon by Double-J Design, used under a Creative Commons Attribution license)
-
Oriented spanners
, , , , , , and .Abstract: Given a point set $P$ and a parameter $t$, a (directed) geometric $t$-spanner $G=(P,E)$ is a subgraph of the complete (bi-directed) graph such that for every pair of points the shortest path in $G$ is at most a factor $t$ longer than the corresponding Euclidean distance.In this paper, we introduce a new model: the oriented (geometric) spanner. This is a directed graph where every edge is one-way, i.e. $(p,p’)\in E \implies (p’,p)\notin E $. We investigate bounds for the minimal dilation. For $2$-dimensional point sets, we prove NP-hardness of computing a minimal oriented dilation graph. For $1$-dimensional point sets, 1-spanners are trivial to obtain. Therefore, we restrict the graphs: We present a dynamic program to compute a $1$-page planar minimal oriented dilation graph in $O(n^8)$ time and a greedy algorithm to compute a constant dilation spanner in $O(n^3)$ time.
39th European Workshop on Computational Geometry (EuroCG 2023), pages 46:1–46:9, 2023.
@article{BGKPRRW2023OrientedEuroCG, author={Buchin, Kevin and Gudmundsson, Joachim and Kalb, Antonia and Popov, Aleksandr and Rehs, Carolin and van Renssen, Andr\'e and Wong, Sampson}, title={Oriented Spanners}, journal={39th European Workshop on Computational Geometry (EuroCG 2023)}, year={2023}, pages={46:1-46:9}, note={abstract} } -
Local routing in a tree metric 1-spanner
, , and .Abstract: Solomon and Elkin [5] constructed a shortcutting scheme for weighted trees which results in a 1-spanner for the tree metric induced by the input tree. The spanner has logarithmic lightness, logarithmic diameter, a linear number of edges and bounded degree (provided the input tree has bounded degree). This spanner has been applied in a series of papers devoted to designing bounded degree, low-diameter, low-weight $(1 + \epsilon)$-spanners in Euclidean and doubling metrics. In this paper, we present a simple local routing algorithm for this tree metric spanner. The algorithm has a routing ratio of 1, is guaranteed to terminate after $O(\log n)$ hops and requires $O(\Delta \log n)$ bits of storage per vertex where $\Delta$ is the maximum degree of the tree on which the spanner is constructed.
36th European Workshop on Computational Geometry (EuroCG 2020), pages 76:1–76:5, 2020.
@article{BGR2020TreeRoutingEuroCG, author={Brankovic, Milutin and Gudmundsson, Joachim and van Renssen, Andr\'e}, title={Local Routing in a Tree Metric 1-Spanner}, journal={36th European Workshop on Computational Geometry (EuroCG 2020)}, year={2020}, pages={76:1-76:5}, note={abstract} } -
Covering a set of line segments with a few squares
, , , , , and .Abstract: We study the problem of covering a set of line segments with a few (up to four) axis-parallel, unit-sized squares in the plane. Covering line segments with two squares has been previously studied, however, little is known for three or more squares. Our original motivation for the line segment covering problem comes from trajectory analysis. We study two trajectory covering problems: a data structure on the trajectory that efficiently answers whether a query subtrajectory is coverable, and an algorithm to compute its longest coverable subtrajectory.
36th European Workshop on Computational Geometry (EuroCG 2020), pages 45:1–45:8, 2020.
@article{GKRSWW2020TrajectoryCoveringEuroCG, author={Gudmundsson, Joachim and van de Kerkhof, Mees and van Renssen, Andr\'e and Staals, Frank and Wiratma, Lionov and Wong, Sampson}, title={Covering a set of line segments with a few squares}, journal={36th European Workshop on Computational Geometry (EuroCG 2020)}, year={2020}, pages={45:1-45:8}, note={abstract} } -
Frechet distance queries in trajectory data
, , , and .Abstract: Let $\pi$ be a trajectory with $n$ vertices in the plane. We show how to preprocess $\pi$ such that given any two points $u$ and $v$ on $\pi$ (not necessarily vertices of $\pi$) and a horizontal query segment $Q$, one can quickly determine the exact Fréchet distance between $Q$ and the subtrajectory from $u$ to $v$. We present a data structure that requires $\mathcal{O}(n^{2}\log^{2} n)$ construction time and space such that queries can be answered in $\mathcal{O}(\log^8 n)$ time.
3rd Iranian Conference on Computational Geometry (ICCG 2020), pages 29–32, 2020.
@article{GRSW2020FrechetICCG, author={Gudmundsson, Joachim and van Renssen, Andr\'e and Saeidi, Zeinab and Wong, Sampson}, title={Frechet Distance Queries in Trajectory Data}, journal={3rd Iranian Conference on Computational Geometry (ICCG 2020)}, year={2020}, pages={29-32}, note={abstract} } -
Reconfiguring edge-connected pivoting modular robots
, , , , , , , , , , and .
XVIII Spanish Meeting on Computational Geometry (EGC 2019), 2019.
@article{AADDDFKPPRS2019RobotsEGC, author={Akitaya, Hugo A. and Arkin, Esther D. and Damian, Mirela and Demaine, Erik D. and Dujmovi\'c, Vida and Flatland, Robin and Korman, Matias and Palop, Belen and Parada, Irene and van Renssen, Andr\'e and Sacrist\'an, Vera}, title={Reconfiguring edge-connected pivoting modular robots}, journal={XVIII Spanish Meeting on Computational Geometry (EGC 2019)}, year={2019}, note={abstract} } -
Routing in histograms
, , , , , , , and .Abstract: Let $P$ be a histogram with $n$ vertices, i.e., an $x$-monotone orthogonal polygon whose upper boundary is a single edge. Two points $p, q \in P$ are co-visible if and only if the (axis-parallel) bounding rectangle of $p$ and $q$ is in $P$. In the $r$-visibility graph of $P$, we connect two vertices of $P$ with an unweighted edge if and only if they are co-visible. We consider routing with preprocessing in $P$. We may preprocess $P$ to obtain a label and a routing table for each vertex of $P$. Then, we must be able to route a packet between any two vertices $s$ and $t$ of $P$, where each step may use only the label of the target node $t$, the routing table, and the neighborhood of the current node.We present a routing scheme for histograms that sends any data packet along a shortest path. Each label needs $O(\log n)$ bits, while the routing table of each node consists of a single bit.
35th European Workshop on Computational Geometry (EuroCG 2019), 2019.
@article{CCHKKMRRW2019HistogramEuroCG, author={Chiu, Man-Kwun and Cleve, Jonas and Klost, Katharina and Korman, Matias and Mulzer, Wolfgang and van Renssen, Andr\'e and Roeloffzen, Marcel and Willert, Max}, title={Routing in Histograms}, journal={35th European Workshop on Computational Geometry (EuroCG 2019)}, year={2019}, note={abstract} } -
Rectilinear link diameter and radius in a rectilinear polygonal domain
, , , , , , and .Abstract: 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 graph of oriented distances to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in $O (\min(n^\omega, n^2 + nh \log h + \chi^2))$ time, where $\omega<2.373$ denotes the matrix multiplication exponent and $\chi \in \Omega(n) \cap O(n^2)$ is the number of edges of the graph of oriented distances. We also provide a faster algorithm for computing the diameter that runs in $O(n^2 \log n)$ time.
34th European Workshop on Computational Geometry (EuroCG 2018), pages 2:1–2:6, 2018.
@article{BKRV2018RectilinearLinkEuroCG, author={Chiu, Man-Kwun and Khramtcova, Elena and Markovic, Aleksandar and Okamoto, Yoshio and Ooms, Aur\'elien and van Renssen, Andr\'e and Roeloffzen, Marcel}, title={Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain}, journal={34th European Workshop on Computational Geometry (EuroCG 2018)}, year={2018}, pages={2:1-2:6}, note={abstract} } -
Routing in polygonal domains
, , , , , , , , and .
20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2017), pages 88–89, 2017.
@article{BKMRRSSVW2017RoutingJCDCG, author={Banyassady, Bahareh and Korman, Matias and Mulzer, Wolfgang and van Renssen, Andr\'e and Roeloffzen, Marcel and Seiferth, Paul and Stein, Yannik and Vogtenhuber, Birgit and Willert, Max}, title={Routing in Polygonal Domains}, journal={20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2017)}, year={2017}, pages={88-89}, note={abstract} } -
Kinetic all-pairs shortest path in a simple polygon
, , , , and .Abstract: We provide a simple data structure to compute all-pairs shortest paths of a given collection of $n$ sites in a simple polygon of $m$ corners. The structure can be maintained as the sites move (in a linear fashion) within the domain. For each event in which the combinatorial structure of the shortest path changes, we spend $O(\log nm)$ time updating our structure. We give upper and lower bounds on the number of such changes, proving that our structure is efficient.
33rd European Workshop on Computational Geometry (EuroCG 2017), pages 21–24, 2017.
@article{DKRRS2017KineticAPSPEuroCG, author={Diez, Yago and Korman, Matias and van Renssen, Andr\'e and Roeloffzen, Marcel and Staals, Frank}, title={Kinetic All-Pairs Shortest Path in a Simple Polygon}, journal={33rd European Workshop on Computational Geometry (EuroCG 2017)}, year={2017}, pages={21-24}, note={abstract} } -
A lower bound for the dynamic conflict-free coloring of intervals with respect to points
, , , , , and .Abstract: We introduce the dynamic conflict-free coloring problem for a set $S$ of intervals in $\mathbb{R}^1$ with respect to points, where the goal is to maintain a conflict-free coloring for $S$ under insertions and deletions. We investigate trade-offs between the number of colors used and the number of intervals that are recolored upon insertion or deletion of an interval. We provide a lower bound on the number of recolorings as a function of the number of colors, which implies that with $O(1)$ recolorings per update the worst-case number of colors is $\Omega(\log n/\log\log n)$, and that any strategy using $O(1/\epsilon)$ colors needs $\Omega(\epsilon n^{\epsilon})$ recolorings. We also provide a stronger lower bound against so-called local algorithms.
33rd European Workshop on Computational Geometry (EuroCG 2017), pages 185–188, 2017.
@article{BLRRMW2017ColoringLBEuroCG, author={de Berg, Mark and Leijsen, Tim and van Renssen, Andr\'e and Roeloffzen, Marcel and Markovic, Aleksandar and Woeginger, Gerhard}, title={A Lower Bound for the Dynamic Conflict-Free Coloring of Intervals with Respect to Points}, journal={33rd European Workshop on Computational Geometry (EuroCG 2017)}, year={2017}, pages={185-188}, note={abstract} } -
Routing in simple polygons
, , , , , , , and .Abstract: A routing scheme $\mathcal{R}$ in a network $G=(V,E)$ is an algorithm that allows to send messages from one node to another in the network. We are first allowed a preprocessing phase in which we assign a unique label to each node $p\in V$ and a routing table with additional information. After this preprocessing, the routing algorithm itself must be local (i.e., we can only use the information from the label of the target and the routing table of the node that we are currently at).We present a routing scheme for routing in simple polygons: for any $\epsilon > 0$ the routing scheme provides a stretch of $1+\epsilon $, labels have $O(\log n)$ bits, the corresponding routing tables are of size $O(\epsilon ^{-1}\log n)$, and the preprocessing time is $O(n^2+\epsilon ^{-1}n)$. This improves the best known strategies for general graphs by Roditty and Tov (Distributed Computing 2016).
33rd European Workshop on Computational Geometry (EuroCG 2017), pages 17–20, 2017.
@article{KMRRSSVW2017RoutingEuroCG, author={Korman, Matias and Mulzer, Wolfgang and van Renssen, Andr\'e and Roeloffzen, Marcel and Seiferth, Paul and Stein, Yannik and Vogtenhuber, Birgit and Willert, Max}, title={Routing in Simple Polygons}, journal={33rd European Workshop on Computational Geometry (EuroCG 2017)}, year={2017}, pages={17-20}, note={abstract} } -
Constrained generalized Delaunay graphs are plane spanners
, , and .
9th Annual Meeting of the Asian Association for Algorithms and Computation (AAAC 2016), 2016.
@article{BCR2016Constrained, author={Bose, Prosenjit and De Carufel, Jean-Lou and van Renssen, Andr\'e}, title={Constrained Generalized {D}elaunay Graphs Are Plane Spanners}, journal={9th Annual Meeting of the Asian Association for Algorithms and Computation (AAAC 2016)}, year={2016}, note={abstract} } -
Time-space trade-offs for triangulating a simple polygon
, , , , and .Abstract: An $s$-workspace algorithm is an algorithm that has read-only access to the values of the input, write-only access to the output and only uses $O(s)$ additional words of space. We give a randomized $s$-workspace algorithm for triangulating a simple polygon $P$ of $n$ vertices, for any $s\in \Omega(\log n)\cap O(n)$. The algorithm runs in $O(n^2/s)$ expected time. We also extend the approach to compute other similar structures such as the shortest-path map (or tree) of any point $p\in P$, or to partition $P$ using only diagonals of the polygon so that the resulting sub-polygons have $\Theta(s)$ vertices each.
32nd European Workshop on Computational Geometry (EuroCG 2016), 2016.
@article{AKPRR2016TriangulatingEuroCG, author={Aronov, Boris and Korman, Matias and Pratt, Simon and van Renssen, Andr\'e and Roeloffzen, Marcel}, title={Time-Space Trade-offs for Triangulating a Simple Polygon}, journal={32nd European Workshop on Computational Geometry (EuroCG 2016)}, year={2016}, note={abstract} } -
On kinetic range spaces and their applications
, , , , , and .Abstract: We study geometric hypergraphs in a kinetic setting and show that for many of the static cases where the $\mathsf{VC}$-dimension of the hypergraph is bounded the kinetic counterpart also has bounded $\mathsf{VC}$-dimension. Among other results we show that for any set of $n$ moving points in $\mathbb R^d$ and any parameter $1 < k < n$, one can select a non-empty subset of the points of size $O(k \log k)$ such that each cell of the Voronoi diagram of this subset is "balanced" at any given time (i.e., it contains $O(n/k)$ of the other points). We also show that the bound is near optimal even for the one-dimensional case in which points move linearly.
32nd European Workshop on Computational Geometry (EuroCG 2016), 2016.
@article{CKKRRS2016InterferenceEuroCG, author={De Carufel, Jean-Lou and Katz, Matya and Korman, Matias and van Renssen, Andr\'e and Roeloffzen, Marcel and Smorodinsky, Shakhar}, title={On Kinetic Range Spaces and their Applications}, journal={32nd European Workshop on Computational Geometry (EuroCG 2016)}, year={2016}, note={abstract} } -
Time-space trade-offs for triangulating a simple polygon
, , , , and .
Fall Workshop on Computational Geometry (FWCG 2015), 2015.
@article{AKPRR2015Triangulating, author={Aronov, Boris and Korman, Matias and Pratt, Simon and van Renssen, Andr\'e and Roeloffzen, Marcel}, title={Time-Space Trade-offs for Triangulating a Simple Polygon}, journal={Fall Workshop on Computational Geometry (FWCG 2015)}, year={2015}, note={abstract} } -
Symmetric assembly puzzles are hard, beyond a few pieces
, , , , , , , , and .
18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG^2 2015), 2015.
@article{DKKMORRUU2015Puzzle, author={Demaine, Erik D. and Korman, Matias and Ku, Jason S. and Mitchell, Joseph and Otachi, Yota and van Renssen, Andr\'e and Roeloffzen, Marcel and Uehara, Ryuhei and Uno, Yushi}, title={Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces}, journal={18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG^2 2015)}, year={2015}, note={abstract} } -
Constrained generalized Delaunay graphs are plane spanners
, , and .Abstract: We look at generalized Delaunay graphs in the constrained setting by introducing line segments which the edges of the graph are not allowed to cross. Given an arbitrary convex shape $C$, an unconstrained Delaunay graph is constructed by adding an edge between two vertices $p$ and $q$ if and only if there exists a homothet of $C$ with $p$ and $q$ on its boundary that does not contain any other vertices. We show that, regardless of the convex shape used to construct the constrained Delaunay graph, there exists a constant $t$ such that it is a plane $t$-spanner.
31st European Workshop on Computational Geometry (EuroCG 2015), pages 176–179, 2015.
@article{BCR2015Constrained, author={Bose, Prosenjit and De Carufel, Jean-Lou and van Renssen, Andr\'e}, title={Constrained Generalized {D}elaunay Graphs Are Plane Spanners}, journal={31st European Workshop on Computational Geometry (EuroCG 2015)}, year={2015}, pages={176-179}, note={abstract} } -
Time-space trade-offs for Voronoi diagrams
, , , , , and .Abstract: Let $S$ be a planar $n$-point set. Classically, one can find the Voronoi diagram $VD(S)$ for $S$ in $O(n \log n)$ time and $O(n)$ space. We study the situation when the available workspace is limited: for $s \in {1, \dots, n}$, an $s$-workspace algorithm has read-only access to an input array with the points from $S$ in arbitrary order, and it may use only $O(s)$ additional words of $O(\log n)$ bits for reading and writing intermediate data. We describe a randomized $s$-workspace algorithm for finding $VD(S)$ in expected time $O((n^2/s) \log s + n \log s \log^*s)$. This almost matches the optimal running times for both constant and linear workspace and provides a continuous trade-off between them.
31st European Workshop on Computational Geometry (EuroCG 2015), pages 248–251, 2015.
@article{KMRRSS2015Voronoi, author={Korman, Matias and Mulzer, Wolfgang and van Renssen, Andr\'e and Roeloffzen, Marcel and Seiferth, Paul and Stein, Yannik}, title={Time-Space Trade-offs for {V}oronoi Diagrams}, journal={31st European Workshop on Computational Geometry (EuroCG 2015)}, year={2015}, pages={248-251}, note={abstract} } -
New and improved stretch factors of Yao graphs
, , , , , , , , , and .Abstract: In this paper we study the stretch factors of Yao graphs. We prove that $Y_5$, the Yao graph with five cones, is a spanner with stretch factor $\rho = 2+\sqrt{3} \approx 3.74$. Since $Y_5$ is the only Yao graph whose status of being a spanner or not was open, this completes the picture of the Yao graphs that are spanners: a Yao graph $Y_k$ is a spanner if and only if $k \geq 4$.We also improve the known stretch factor of all the Yao graphs for odd $k > 5$ and reduce the known stretch factor of $Y_6$ from 17.7 to 5.8.
We complement the above results with a lower bound of 2.87 on the stretch factor of $Y_5$. We also show that $Y Y_5$, the Yao-Yao graph with five cones, is not a spanner.
Fall Workshop on Computational Geometry (FWCG 2013), 2013.
@article{BBDFKORTVX2013Yao, author={Barba, Luis and Bose, Prosenjit and Damian, Mirela and Fagerberg, Rolf and Keng, Wah Loon and O'Rourke, Joseph and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander and Xia, Ge}, title={New and Improved Stretch Factors of {Y}ao Graphs}, journal={Fall Workshop on Computational Geometry (FWCG 2013)}, year={2013}, note={abstract} }
Multidisciplinary Papers
Extended abstracts that I presented are marked with .
(Icon by Double-J Design, used under a Creative Commons Attribution license)
-
Multi-hop driver-parcel matching with dynamic network partitioning: When is it more beneficial to split trips in on-demand logistics services?
, , and .Abstract: On-demand logistics services enable customers to place parcel orders online within a prescribed delivery time window. The surge in parcel volume poses significant challenges to meeting service expectations and uncertain demands. To optimize delivery efficiency, a common practice is to use a single-hop delivery approach, where no intermediate parcel transfer is allowed. This approach may result in under-utilization of supply capacities and hamper the ability to service parcels effectively. Multi-hop delivery, on the other hand, allows parcels to transfer between couriers in a single trip, making greater use of existing capacities and creating service opportunities that were previously unattainable. Under the assumption that couriers prefer to operate within smaller geographic areas to enhance their efficiency for local pickups and drop-offs, this paper addresses the real-time multi-hop delivery problem. The service area is divided into smaller courier regions, and each courier is assigned to a specific region, performing delivery tasks exclusively within their designated region. A set of accessible lockers is assumed to be placed on the edges of these regions, serving as transfer nodes. We propose two-phase heuristic algorithms, Dynamic Programming, and Earliest-Completion-Time (ECT) algorithms, to tackle the multi-hop delivery problem. Experimental results for realistic settings demonstrate the advantages of multi-hop delivery services with pre-assigned courier operating regions. Our proposed methods outperform the single-hop delivery benchmark significantly, achieving more courier-parcel matchings, reducing total travel distance, and simultaneously enhancing customer satisfaction.
27th International Conference of Hong Kong Society for Transportation Studies (HKSTS), 2023.
@article{YRR2023MultiHop, author={Yang, Yue and Ramezani, Mohsen and van Renssen, Andr\'e}, title={Multi-hop driver-parcel matching with dynamic network partitioning: {W}hen is it more beneficial to split trips in on-demand logistics services?}, journal={27th International Conference of Hong Kong Society for Transportation Studies (HKSTS)}, year={2023}, note={multi} } -
On utilization bounds for a periodic resource under rate monotonic scheduling
, , , , and .Abstract: This paper revisits utilization bounds for a periodic resource under the rate monotonic (RM) scheduling algorithm. We show that the existing utilization bound, as presented in [8, 9], is optimistic. We subsequently show that by viewing the unavailability of the periodic resource as a deferrable server at highest priority, existing utilization bounds for systems with a deferrable server [3, 11] can be reused. Moreover, using this view, the utilization bound presented in [7] for hierarchical fixed-priority scheduling turns out to be similar to the bound in [3].
Proceedings of the Work-in-Progress session of the 21st Euromicro Conference on Real-Time Systems (ECRTS 2009), pages 25–28, 2009.
@article{RGHPB2009Utilization, author={van Renssen, Andr\'e and Geuns, Stefan and Hausmans, Joost and Poncin, Wouter and Bril, Reinder}, title={On utilization bounds for a periodic resource under rate monotonic scheduling}, journal={Proceedings of the Work-in-Progress session of the 21st Euromicro Conference on Real-Time Systems (ECRTS 2009)}, year={2009}, pages={25--28}, note={multi} }
Computer Science Education Papers
Extended abstracts that I presented are marked with .
(Icon by Double-J Design, used under a Creative Commons Attribution license)
-
Designing problem sessions for algorithmic subjects to boost student confidence
.Abstract: In this paper, we describe how we changed the structure of problem sessions in an algorithmic subject, in order to improve student confidence. The subject in question is taught to very large cohorts of (around 900) students, though our approach can be applied more broadly. We reflect on our experiences over a number of years, including during the pandemic, and show that by adding clear sectioning indicating the style of the questions and by including simple warm-up questions, student engagement and confidence improves, while making the teaching activities of our teaching assistants easier to manage.
In Proceedings of the 26th Australasian Computing Education Conference (ACE 2024), pages 164–171, 2024.
@inproceedings{R2024Confidence, author={van Renssen, Andr\'e}, title={Designing Problem Sessions for Algorithmic Subjects to Boost Student Confidence}, booktitle={Proceedings of the 26th Australasian Computing Education Conference (ACE 2024)}, year={2024}, pages={164-171}, note={education}, doi={10.1145/3636243.3636261} }
Theses
-
Theta-graphs and other constrained spanners
.Abstract: We provide improved upper bounds on the spanning ratio of various geometric graphs, one of which being $\theta$-graphs. Given a set of points in the plane, a $\theta$-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $\theta = 2 \pi/m$, and adds an edge to the ‘closest’ vertex in each cone. We provide tight bounds on a large number of these graphs, for different values of $m$, and improve the upper bounds on the other $\theta$-graphs.We also study the ordered setting, where the $\theta$-graph is built by inserting vertices one at a time and we consider only previously-inserted vertices when determining the ‘closest’ vertex in each cone. We improve some of the upper bounds in this setting, but our main contribution is that we show that a number of $\theta$-graphs that are spanners in the unordered setting are not spanners in the ordered setting.
Our main topic, however, is the constrained setting: We introduce line segment constraints that the edges of the graph are not allowed to cross and show that the upper bounds shown for $\theta$-graphs carry over to constrained $\theta$-graphs. We also construct a bounded-degree plane spanner based on the constrained \halfgraph (the constrained Delaunay graph whose empty convex shape is an equilateral triangle) and we provide a local competitive routing algorithm for the constrained $\theta_6$-graph.
Next, we look at constrained Yao-graphs, which are comparable to constrained $\theta$-graphs, but use a different distance function, and show that these graphs are spanners.
Finally, we look at constrained generalized Delaunay graphs: Delaunay graphs where the empty convex shape is not necessarily a circle, but can be any convex shape. We show that regardless of the convex shape, these graphs are connected, plane spanners. We then proceed to improve the spanning ratio for a subclass of these graphs, where the empty convex shape is an arbitrary rectangle.
PhD thesis, Carleton University, 2014.
@phdthesis{R2014ConstrainedSpanners, author={van Renssen, Andr\'e}, title={Theta-Graphs and Other Constrained Spanners}, type={PhD thesis}, school={Carleton University}, year={2014} } -
The 2$\times$2 simple packing problem
.Abstract: We study the 2$\times$2 simple packing problem: given a simple rectilinear grid polygon $P$ consisting of $n$ edges and containing $N$ cells, we want to know the maximum number of non-overlapping, axis-aligned 2$\times$2 squares we can pack in $P$. Fractional placement of the squares is not allowed. When $P$ contains holes, the problem has been proven to be NP-complete. Whether the 2$\times$2 simple packing problem can be solved in polynomial time or is NP-hard is a major open question in the area of packing problems.We consider a number of techniques to solve this problem, including a transformation to a well-known graph problem: the Maximum Independent Set Problem. In general graphs this problem is NP-complete. But with the specific graphs we use (the intersection graph of all possible squares that can be placed in the polygon), a number of classes of polygons can be solved using this method. The graphs we construct to solve the packing problem, however, can be very large: their number of vertices is proportional to the number of squares of the optimal solution of the Maximum Independent Set Problem, but it remains open whether it is polynomial in $n$.
Using the results obtained from the graph, we describe specific configurations of edges in the polygon that always give rise to the same number of squares in the optimal solution. We describe a simple algorithm that uses these configurations to solve certain classes of polygons in $O(n^2)$ time. Since not all simple polygons can be solved using this technique, we also provide a construction scheme for polygons that can be solved.
Finally, we improve the running time of the 1/2-approximation algorithm described by Berman et al. [8]. This approximation algorithm works on any polygon, by repeatedly placing a square in the lexicographically smallest location in the polygon. The running time is reduced from $O(N)$ to $O(n^2)$. We also sketch a 1/2-approximation algorithm that runs in $O(n \log n)$ time.
Master’s thesis, Eindhoven University of Technology, 2010.
@mastersthesis{R2010Packing, author={van Renssen, Andr\'e}, title={The 2$\times$2 Simple Packing Problem}, type={Master's thesis}, school={Eindhoven University of Technology}, year={2010} }