This list is also available as plain text or BibTeX.
@article{BCR2018GeneralizedDelaunayJournal, author={Bose, Prosenjit and De Carufel, Jean-Lou and van Renssen, Andr\'e}, title={Constrained Generalized {D}elaunay Are Plane Spanners}, year={2018}, journal={ArXiv e-prints}, archivePrefix={arXiv}, eprint={1602.07365}, note={\href{http://arxiv.org/abs/1602.07365}{arXiv:1602.07365}}, url={http://arxiv.org/abs/1602.07365} }
@article{BLMRRW2018ColoringJournal, 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}, year={2018}, journal={ArXiv e-prints}, archivePrefix={arXiv}, eprint={1701.03388}, note={\href{http://arxiv.org/abs/1701.03388}{arXiv:1701.03388}}, url={http://arxiv.org/abs/1701.03388} }
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.
@article{DKRR2018GrowingDisksJournal, 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}, year={2018}, journal={ArXiv e-prints}, archivePrefix={arXiv}, eprint={1704.07580}, note={\href{http://arxiv.org/abs/1704.07580}{arXiv:1704.07580}}, url={http://arxiv.org/abs/1704.07580} }
For any fixed $\epsilon > 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 + \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)$. It can be improved to $O(n^2)$ for simple polygons.
@article{BKMRRSSVW2017RoutingJournal, 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}, year={2017}, journal={ArXiv e-prints}, archivePrefix={arXiv}, eprint={1703.09533}, note={\href{http://arxiv.org/abs/1703.09533}{arXiv:1703.09533}}, url={http://arxiv.org/abs/1703.09533} }
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.
@article{BKRV2017RoutingJournal, author={Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Verdonschot, Sander}, title={Constrained Routing Between Non-Visible Vertices}, year={2017}, journal={ArXiv e-prints}, archivePrefix={arXiv}, eprint={1710.08060}, note={\href{http://arxiv.org/abs/1710.08060}{arXiv:1710.08060}}, url={http://arxiv.org/abs/1710.08060} }
@article{CCKKORRSS2017LineSeparatorJournal, 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}, year={2017}, journal={ArXiv e-prints}, archivePrefix={arXiv}, eprint={1709.02579}, note={\href{http://arxiv.org/abs/1709.02579}{arXiv:1709.02579}}, url={http://arxiv.org/abs/1709.02579} }
@article{BCKLRRV2017ColoringJournal, 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}, year={2017}, journal={ArXiv e-prints}, archivePrefix={arXiv}, eprint={1708.09080}, note={\href{http://arxiv.org/abs/1708.09080}{arXiv:1708.09080}}, url={http://arxiv.org/abs/1708.09080} }
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(P)$ and $FVD(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 can compute the family of all higher-order Voronoi diagrams of order $k = 1, \dots, K$ for $P$ in total 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((n^2/s) \log s + n \log s \log^*s)$ [Korman et al., WADS’15] and only works for $NVD(P)$ (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.
@article{BKRV2017VoronoiJournal, 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}, year={2017}, journal={ArXiv e-prints}, archivePrefix={arXiv}, eprint={1708.00814}, note={\href{http://arxiv.org/abs/1708.00814}{arXiv:1708.00814}}, url={http://arxiv.org/abs/1708.00814} }
@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} }
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.
@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} }
@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} }
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.
@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} }
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$.
@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}, journal={Computational Geometry: Theory and Applications (CGTA)}, year={2018}, volume={67}, pages={42-52}, doi={10.1016/j.comgeo.2017.10.002} }
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]|$.
@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} }
@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} }
@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} }
@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} }
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.
@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} }
@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} }
@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} }
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.
@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} }
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.
@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} }
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.
@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} }
@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} }
@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} }
@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} }
Conference papers that I presented are marked with .
(Icon by Double-J Design, used under a Creative Commons Attribution license)
@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} }
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.
@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} }
@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} }
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.
@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} }
@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} }
@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} }
@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} }
@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} }
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.
@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} }
@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} }
@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} }
@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} }
@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} }
@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} }
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$).
@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} }
@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} }
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.
@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} }
@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} }
@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} }
@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} }
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$.
@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} }
@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} }
@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} }
@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} }
@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} }
@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} }
@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} }
@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} }
@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} }
@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} }
@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} }
@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} }
@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} }
@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} }
@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} }
Extended abstracts that I presented are marked with .
(Icon by Double-J Design, used under a Creative Commons Attribution license)
@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}, note={abstract} }
@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} }
@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} }
@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} }
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).
@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} }
@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} }
@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} }
@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} }
@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} }
@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} }
@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} }
@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} }
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.
@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} }
@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} }
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.
@phdthesis{R2014ConstrainedSpanners, author={van Renssen, Andr\'e}, title={Theta-Graphs and Other Constrained Spanners}, type={PhD thesis}, school={Carleton University}, year={2014} }
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.
@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} }
Generated by Publy 1.1. Last modified on 15 February 2018.