The authors are sorted by their last name, as is custom in my field. All papers (except a minor Real-Time Systems result) follow this convention.

This list is also available as plain text or BibTeX.

## Currently Under Review

• #### Snipperclips

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.
, , , and .
Submitted to the 29th Canadian Conference on Computational Geometry (CCCG 2017).
• #### On plane constrained bounded-degree spanners

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.
, , , and .
Submitted to Algorithmica.
@article{BFRV2017ConstrainedBoundedJournal,
author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander},
title={On Plane Constrained Bounded-Degree Spanners},
year={2017},
journal={ArXiv e-prints},
archivePrefix={arXiv},
eprint={1704.03596},
note={\href{http://arxiv.org/abs/1704.03596}{arXiv:1704.03596}},
url={http://arxiv.org/abs/1704.03596}
}
• #### Packing short plane spanning trees in complete geometric graphs

Abstract: Given a set of points in the plane, we want to establish a connection network between these points that consists of several disjoint layers. Motivated by 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 graphs. Then we show a constant factor approximation for a distributed model in which each point can compute its adjacencies using only local information. In both cases the obtained layers are plane.

, , , , , , , and .
Submitted to Computational Geometry: Theory and Applications (CGTA).
@article{AHKPRRRV2017SpanningTreesJournal,
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},
year={2017},
journal={ArXiv e-prints},
archivePrefix={arXiv},
eprint={1703.05863},
note={\href{http://arxiv.org/abs/1703.05863}{arXiv:1703.05863}},
url={http://arxiv.org/abs/1703.05863}
}
• #### Symmetric assembly puzzles are hard, beyond a few pieces

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.
, , , , , , , , and .
Submitted to Computational Geometry: Theory and Applications (CGTA).
@article{DKKMORRUU2017PuzzleJournal,
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},
year={2017},
journal={ArXiv e-prints},
archivePrefix={arXiv},
eprint={1703.02671},
note={\href{http://arxiv.org/abs/1703.02671}{arXiv:1703.02671}},
url={http://arxiv.org/abs/1703.02671}
}
• #### Continuous Yao graphs

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$.

, , , , , , , , , and .
Submitted to Computational Geometry: Theory and Applications (CGTA).
@article{BBBCDFFRTV2017Continuous,
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},
year={2017},
journal={ArXiv e-prints},
archivePrefix={arXiv},
eprint={1408.4099},
note={\href{http://arxiv.org/abs/1408.4099}{arXiv:1408.4099}},
url={http://arxiv.org/abs/1408.4099}
}
• #### Spanning properties of Yao and $\Theta$-graphs in the presence of constraints

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.

and .
Submitted to International Journal of Computational Geometry & Applications (IJCGA).

## Journal Papers

• #### Upper and lower bounds for online routing on Delaunay triangulations

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 \emph{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]|$.

, , , , and .
Accepted to Discrete & Computational Geometry (DCG).
@article{BBCPR2016DelaunayJournal,
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={2016},
doi={10.1007/s00454-016-9842-y}
}

• #### Time-space trade-offs for triangulations and Voronoi diagrams

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)$.
, , , , , and .
Accepted to Computational Geometry: Theory and Applications (CGTA) special issue of EuroCG 2015.
@article{KMRRSS2017VoronoiJournal,
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={2017},
doi={10.1016/j.comgeo.2017.01.001}
}

• #### Competitive local routing with constraints

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.
, , , and .
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

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.
, , , , and .
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

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.
, , , , , and .
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

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.

, , , , , , , and .
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

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.
, , and .
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

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.
, , , and .
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

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.

, , , , and .
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

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.

, , , and .
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

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.

, , , , , , , , , and .
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

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$.
, , , and .
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

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.
, , , , , , , and .
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

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$.
, , , , and .
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 .

• #### Constrained routing between non-visible vertices

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 $T$, which is optimal in the worst case, given the lower bound.
, , , and .
Accepted to the 23rd Annual International Computing and Combinatorics Conference (COCOON 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}
}

• #### Dynamic graph coloring

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} dN^{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(dN^{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.
, , , , , , and .
Accepted to the 15th Algorithms and Data Structures Symposium (WADS 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}
}

• #### Balanced line separators of unit disk graphs

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 separator of sublinear size exists when we look at disks of arbitrary radii. 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})$).
, , , , , , , , and .
Accepted to the 15th Algorithms and Data Structures Symposium (WADS 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}
}

• #### Improved time-space trade-offs for computing Voronoi diagrams and triangulations

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.

, , , , , , and .
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 and Triangulations},
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

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.
, , , , , , , and .
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

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.
, , , , , , , , and .
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

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.
, , and .
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

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.
, , , , , and .
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

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.
, , , , and .
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

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$).

, , , , , , , and .
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

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.
, , , and .
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

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.

, , , , and .
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

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.
, , and .
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

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)$.
, , , , , and .
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

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.
, , and .
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

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$.

, , , , , , , and .
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

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$.
, , , , , , , , , and .
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

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.
and .
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

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.
, , , , and .
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

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.
, , and .
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

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.
, , , , , , , and .
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

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$.
, , , and .
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

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.
, , , , and .
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

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.
, , , and .
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

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.
, , , and .
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

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.
, , , and .
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

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.
, , , , and .
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

Abstract: We significantly extend the class of polygons for which the 2$\times$2 Simple Packing Problem can be solved in polynomial time.
and .
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

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.
, , and .
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}
}


## Other Publications

Extended abstracts that I presented are marked with .

• #### Kinetic all-pairs shortest path in a simple polygon

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.
, , , , and .
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

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.
, , , , , and .
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

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).

, , , , , , , and .
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

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.
, , , , and .
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

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.
, , , , , and .
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

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.
, , and .
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

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.
, , , , , and .
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},
journal={31st European Workshop on Computational Geometry (EuroCG 2015)},
year={2015},
pages={248-251},
note={abstract}
}

• #### New and improved stretch factors of Yao graphs

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.

, , , , , , , , , and .
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}
}

• #### On utilization bounds for a periodic resource under rate monotonic scheduling

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].
, , , , and .
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={abstract}
}


## 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}
}