This list is also available as plain text or BibTeX.
We present two algorithms to maintain an approximation of the optimal coloring that, together, present a trade-off between the number of recolorings and the number of colors used: For any $d>0$, the first algorithm maintains a proper $O(\mathcal{C} d N^1/d)$-coloring and recolors at most $O(d)$ vertices per update. The second maintains an $O(\mathcal{C} d)$-coloring using $O(d N^1/d)$ recolorings per update. Both algorithms achieve the same asymptotic performance when $d = \log N$.
Moreover, we show that for any algorithm that maintains a $c$-coloring of a $2$-colorable graph on $N$ vertices during a sequence of $m$ updates, there is a sequence of updates that forces the algorithm to recolor at least $\Omega(m\cdot N^\frac{2}{c(c-1)})$ vertices.
@article{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}, year={2016}, journal={ArXiv e-prints}, archivePrefix={arXiv}, eprint={1507.02130}, note={\href{http://arxiv.org/abs/1507.02130}{arXiv:1507.02130}}, url={http://arxiv.org/abs/1507.02130} }
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{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}, year={2016}, journal={ArXiv e-prints}, archivePrefix={arXiv}, eprint={1501.01783}, note={\href{http://arxiv.org/abs/1501.01783}{arXiv:1501.01783}}, url={http://arxiv.org/abs/1501.01783} }
@article{KMRRSS2016VoronoiJournal, 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={2016} }
@article{BMR2016OrderJournal, 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={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} }
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} }
@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{DKKMORRUU2015PuzzleProc, 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={2015} }
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} }
@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} }
@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{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.0. Last modified on 23 May 2016.