People_

Dr Andre van Renssen

Ph.D. Computer Science, Carleton University (Canada)

Senior Lecturer
School of Computer Science

Email

andre.vanrenssen@sydney.edu.au

Address

J12 - Computer Science Building

The University of Sydney

Websites

School of Computer Science

Sydney Algorithms and Computing Theory (SACT) research group

Personal Webpage

Research interests

Dr André van Renssen's research focuses on calculating the shortest possible paths through various types of networks - from computer and communications networks to road and other transport networks. By designing routing algorithms that can perform this task quickly and efficiently, he aims to help alleviate both information and vehicle traffic congestion without the need to build more roads or add more cables.

"The main purpose of the networks I study is to allow either information or traffic to move from one node (location) to another. So we need to find the shortest paths between the various nodes. My research focuses on designing efficient algorithms that can determine which node to direct information or traffic to so it reaches its destination in the shortest possible time.

"The problem of finding the fastest route between two locations depends on the state of the network. If there's a lot of communication or traffic over a certain cable or road, additional traffic that intends to use this route will have to wait its turn. This can be solved by adding more cables or building more or wider roads, but that approach is both expensive and impractical. By designing better routing algorithms, I hope to help alleviate these problems without the need to add new cables or roads.

"The time it takes to get from one location to another may also vary depending on the time or day of the week. During rush hour it might be better to take a longer route using side roads than to take the shortest route, which might be fine on weekends. Other factors, such as lanes being closed due to an accident or construction work, must also be taken into account by the algorithm.

"Results from this kind of research are already being used in, for example, the navigation function of Google Maps, which updates routes when a certain road is congested. I hope my work will lead to even fewer or shorter delays in the future.

"I've been working in this field since around 2010, and I joined the University of Sydney in 2018. I'm very eager to start working with my colleagues here and to expand my research."

FOR Codes

080201 Analysis of Algorithms and Complexity

Current research students

Project title	Research student
Utilisation of Realistic Input Models and the Computation of Their Input Parameters	Zijin HUANG
Spanners and Routing in Computational Geometry	Shuei SAKAGUCHI

Publications

By Type

Expand all

Journals

Aichholzer, O., Korman, M., Okamoto, Y., Parada, I., Perz, D., van Renssen, A., Vogtenhuber, B. (2023). Graphs with large total angular resolution. Theoretical Computer Science, 943, 73-88. [More Information]
Korman, M., van Renssen, A., Roeloffzen, M., Staals, F. (2023). KINETIC GEODESIC VORONOI DIAGRAMS IN A SIMPLE POLYGON. SIAM Journal on Discrete Mathematics, 37(4), 2276-2311. [More Information]
Gudmundsson, J., van de Kerkhof, M., van Renssen, A., Staals, F., Wiratma, L., Wong, S. (2022). Covering a set of line segments with a few squares. Theoretical Computer Science, 923, 74-98. [More Information]
Brankovic, M., Gudmundsson, J., van Renssen, A. (2022). Local routing in a tree metric 1-spanner. Journal of Combinatorial Optimization, 44(4), 2642-2660. [More Information]
Ashvinkumar, V., Gudmundsson, J., Levcopoulos, C., Nilsson, B., van Renssen, A. (2022). Local Routing in Sparse and Lightweight Geometric Graphs. Algorithmica, 84(5), 1316-1340. [More Information]
van Renssen, A., Wong, G. (2021). Bounded-Degree Spanners in the Presence of Polygonal Obstacles. Theoretical Computer Science, 854, 159-173. [More Information]
Bose, P., Korman, M., van Renssen, A., Verdonschot, S. (2021). Constrained routing between non-visible vertices. Theoretical Computer Science, 861, 144-154. [More Information]
Arseneva, E., Chiu, M., Korman, M., Markovic, A., Okamoto, Y., Ooms, A., van Renssen, A., Roeloffzen, M. (2021). Rectilinear link diameter and radius in a rectilinear polygonal domain. Computational Geometry: Theory and Applications, 92, 1-11. [More Information]
Abel, Z., Akitaya, H., Chiu, M., Demaine, E., Demaine, M., Hesterberg, A., Korman, M., Lynch, J., van Renssen, A., Roeloffzen, M. (2021). Snipperclips: Cutting tools into desired polygons using themselves. Computational Geometry: Theory and Applications, 98, 101784. [More Information]
Gudmundsson, J., van Renssen, A., Saeidi, Z., Wong, S. (2021). Translation Invariant Fréchet Distance Queries. Algorithmica, 83(11), 3514-3533. [More Information]
Akitaya, H., Arkin, E., Damian, M., Demaine, E., Dujmovic, V., Flatland, R., Korman, M., Palop, B., Parada, I., van Renssen, A., et al (2021). Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers. Algorithmica, 83(5), 1316-1351. [More Information]
Carmi, P., Chiu, M., Katz, M., Korman, M., Okamoto, Y., van Renssen, A., Roeloffzen, M., Shiitada, T., Smorodinsky, S. (2020). Balanced line separators of unit disk graphs. Computational Geometry: Theory and Applications, 86, 1-14. [More Information]
Banyassady, B., Chiu, M., Korman, M., Mulzer, W., van Renssen, A., Roeloffzen, M., Seiferth, P., Stein, Y., Vogtenhuber, B., Willert, M. (2020). Routing in Polygonal Domains. Computational Geometry: Theory and Applications, 87, 101593. [More Information]
Demaine, E., Korman, M., Ku, J., Mitchell, J., Otachi, Y., van Renssen, A., Roeloffzen, M., Uehara, R., Uno, Y. (2020). Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces. Computational Geometry: Theory and Applications, 90, 101648. [More Information]
Barba, L., Cardinal, J., Korman, M., Langerman, S., van Renssen, A., Roeloffzen, M., Verdonschot, S. (2019). Dynamic Graph Coloring. Algorithmica, 81(4), 1319-1341. [More Information]
Ahn, H., Bae, S., Choi, J., Korman, M., Mulzer, W., Oh, E., Park, J., van Renssen, A., Vigneron, A. (2019). Faster Algorithms for Growing Prioritized Disks and Rectangles. Computational Geometry: Theory and Applications, 80, 23-39. [More Information]
de Berg, M., Leijsen, T., Markovic, A., van Renssen, A., Roeloffzen, M., Woeginger, G. (2019). Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points. International Journal of Computational Geometry and Applications, 29(1), 49-72. [More Information]
Kraaijer, R., van Kreveld, M., Meulemans, W., van Renssen, A. (2019). Geometry and Generation of a New Graph Planarity Game. Journal of Graph Algorithms and Applications, 23(4), 603-624. [More Information]
Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S. (2019). On Plane Constrained Bounded-Degree Spanners. Algorithmica, 81(4), 1392-1415. [More Information]
Aichholzer, O., Hackl, T., Korman, M., Pilz, A., van Renssen, A., Roeloffzen, M., Rote, G., Vogtenhuber, B. (2019). Packing Plane Spanning Graphs with Short Edges in Complete Geometric Graphs. Computational Geometry: Theory and Applications, 82, 1-15. [More Information]
Bose, P., van Renssen, A. (2019). Spanning Properties of Yao and Theta-Graphs in the Presence of Constraints. International Journal of Computational Geometry and Applications, 29(2), 95-120. [More Information]
Bose, P., De Carufel, J., van Renssen, A. (2018). Constrained generalized Delaunay graphs are plane spanners. Computational Geometry: Theory and Applications, 74, 50-65. [More Information]
Bakhshesh, D., Barba, L., Bose, P., De Carufel, J., Damian, M., Fagerberg, R., Farshi, M., van Renssen, A., Taslakian, P., Verdonschot, S. (2018). Continuous Yao graphs. Computational Geometry: Theory and Applications, 67, 42-52. [More Information]
Banyassady, B., Korman, M., Mulzer, W., van Renssen, A., Roeloffzen, M., Seiferth, P., Stein, Y. (2018). Improved Time-Space Trade-offs for Computing Voronoi Diagrams. Journal of Computational Geometry, 9(1), 191-212.
Bose, P., Korman, M., van Renssen, A., Verdonschot, S. (2018). Routing on the Visibility Graph. Journal of Computational Geometry, 9(1), 430-453. [More Information]
Korman, M., Mulzer, W., van Renssen, A., Roeloffzen, M., Seiferth, P., Stein, Y. (2018). Time-Space Trade-offs for Triangulations and Voronoi Diagrams. Computational Geometry: Theory and Applications, 73, 35-45. [More Information]
Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S. (2017). Competitive Local Routing with Constraints. Journal of Computational Geometry, 8(1), 125-152. [More Information]
Baffier, J., Chiu, M., Diez, Y., Korman, M., Mitsou, V., van Renssen, A., Roeloffzen, M., Uno, Y. (2017). Hanabi is NP-hard, even for cheaters who look at their cards. Theoretical Computer Science, 675, 43-55. [More Information]
De Carufel, J., Katz, M., Korman, M., van Renssen, A., Roeloffzen, M., Smorodinsky, S. (2017). On interference among moving sensors and related problems. Journal of Computational Geometry, 8(1), 32-46. [More Information]
Aronov, B., Korman, M., Pratt, S., van Renssen, A., Roeloffzen, M. (2017). Time-Space Trade-offs for Triangulating a Simple Polygon. Journal of Computational Geometry, 8(1), 105-124. [More Information]
Bonichon, N., Bose, P., De Carufel, J., Perkovic, L., van Renssen, A. (2017). Upper and Lower Bounds for Online Routing on Delaunay Triangulations. Discrete and Computational Geometry, 58(2), 482-504. [More Information]
Buchin, K., Meulemans, W., van Renssen, A., Speckmann, B. (2016). Area-Preserving Simplification and Schematization of Polygonal Subdivisions. ACM Transactions on Spatial Algorithms and Systems, 2(1), 2. [More Information]
Bose, P., Morin, P., van Renssen, A. (2016). The Price of Order. International Journal of Computational Geometry and Applications, 26(43193), 135-149. [More Information]
Bose, P., De Carufel, J., Morin, P., van Renssen, A., Verdonschot, S. (2016). Towards tight bounds on theta-graphs: More is not always better. Theoretical Computer Science, 616, 70-93. [More Information]
Barba, L., Bose, P., Damian, M., Fagerberg, R., Keng, W., O'Rourke, J., van Renssen, A., Taslakian, P., Verdonschot, S., Xia, G. (2015). New and Improved Spanning Ratios for Yao Graphs. Journal of Computational Geometry, 6(2), 19-53.
Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S. (2015). Optimal local routing on Delaunay triangulations defined by empty equilateral triangles. SIAM Journal on Computing, 44(6), 1626-1649. [More Information]
Aichholzer, O., Bae, S., Barba, L., Bose, P., Korman, M., van Renssen, A., Taslakian, P., Verdonschot, S. (2015). Reprint of: Theta-3 is connected. Computational Geometry: Theory and Applications, 48(5), 407-414. [More Information]
Bose, P., Morin, P., van Renssen, A., Verdonschot, S. (2015). The Theta-5-graph is a spanner. Computational Geometry: Theory and Applications, 48(2), 108-119. [More Information]
Bose, P., Jansens, D., van Renssen, A., Saumell, M., Verdonschot, S. (2014). Making triangulations 4-connected using flips. Computational Geometry: Theory and Applications, 47(2), 187-197. [More Information]
Aichholzer, O., Bae, S., Barba, L., Bose, P., Korman, M., van Renssen, A., Taslakian, P., Verdonschot, S. (2014). Theta-3 is connected. Computational Geometry: Theory and Applications, 47(9), 910-917. [More Information]

show 37 more

Conferences

Gudmundsson, J., van de Kerkhof, M., van Renssen, A., Staals, F., Wiratma, L., Wong, S. (2021). Covering a Set of Line Segments with a Few Squares. 12th International Conference on Algorithms and Complexity, CIAC 2021, Cham: Springer. [More Information]
Brankovic, M., Grujic, N., van Renssen, A., Seybold, M. (2020). A simple dynamization of trapezoidal point location in planar subdivisions. 47th International Colloquium on Automata, Languages and Programming (ICALP 2020), Wadern: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
van Renssen, A., Wong, G. (2020). Bounded-Degree Spanners in the Presence of Polygonal Obstacles. 26th International Computing and Combinatorics Conference (COCOON 2020), Cham: Springer. [More Information]
Korman, M., van Renssen, A., Roeloffzen, M., Staals, F. (2020). Kinetic geodesic Voronoi diagrams in a simple polygon. 47th International Colloquium on Automata, Languages and Programming (ICALP 2020), Wadern: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
Brankovic, M., Gudmundsson, J., van Renssen, A. (2020). Local Routing in a Tree Metric 1-Spanner. 26th International Computing and Combinatorics Conference (COCOON 2020), Cham: Springer. [More Information]
Chiu, M., Cleve, J., Klost, K., Korman, M., Mulzer, W., van Renssen, A., Roeloffzen, M., Willert, M. (2020). Routing in Histograms. 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020), Cham: Springer. [More Information]
Aichholzer, O., Korman, M., Okamoto, Y., Parada, I., Perz, D., van Renssen, A., Vogtenhuber, B. (2019). Graphs with Large Total Angular Resolution. 27th International Symposium on Graph Drawing and Network Visualization (GD 2019), Cham: Springer. [More Information]
Ashvinkumar, V., Gudmundsson, J., Levcopoulos, C., Nilsson, B., van Renssen, A. (2019). Local Routing in Sparse and Lightweight Geometric Graphs. 30th International Symposium on Algorithms and Computation (ISAAC 2019), Saarbrucken/Wadern: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
Akitaya, H., Arkin, E., Damian, M., Demaine, E., Dujmovic, V., Flatland, R., Korman, M., Palop, B., Parada, I., van Renssen, A., et al (2019). Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers. 27th Annual European Symposium on Algorithms (ESA 2019), Munich: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. [More Information]
Kraaijer, R., van Kreveld, M., Meulemans, W., van Renssen, A. (2018). Geometry and Generation of a new Graph Planarity Game. IEEE Conference on Computational Intelligence and Games (CIG 2018), Maastricht: IEEE Computer Society. [More Information]
Arseneva, E., Chiu, M., Korman, M., Markovic, A., Okamoto, Y., Ooms, A., van Renssen, A., Roeloffzen, M. (2018). Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain. 29th International Symposium on Algorithms and Computation (ISAAC 2018), Germany: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
Carmi, P., Chiu, M., Katz, M., Korman, M., Okamoto, Y., van Renssen, A., Roeloffzen, M., Shiitada, T., Smorodinsky, S. (2017). Balanced line separators of unit disk graphs. 15th International Symposium on Algorithms and Data Structures (WADS 2017), Cham: Springer International Publishing. [More Information]
Bose, P., De Carufel, J., van Renssen, A. (2017). Constrained generalized Delaunay graphs are plane spanners. International Conference on Computational Intelligence in Information Systems (CIIS 2016), Cham: Springer. [More Information]
Bose, P., Korman, M., van Renssen, A., Verdonschot, S. (2017). Constrained routing between non-visible vertices. 23rd International Conference on Computing and Combinatorics (COCOON 2017), Hong Kong: Springer. [More Information]
Barba, L., Cardinal, J., Korman, M., Langerman, S., van Renssen, A., Roeloffzen, M., Verdonschot, S. (2017). Dynamic graph coloring. 15th International Symposium on Algorithms and Data Structures (WADS 2017), Cham: Springer International Publishing. [More Information]
Ahn, H., Bae, S., Choi, J., Korman, M., Mulzer, W., Oh, E., Park, J., van Renssen, A., Vigneron, A. (2017). Faster algorithms for growing prioritized disks and rectangles. 28th International Symposium on Algorithms and Computation (ISAAC 2017), Dagstuhl, Germany: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
de Berg, M., Leijsen, T., Merkovic, A., van Renssen, A., Roeloffzen, M., Woeginger, G. (2017). Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points. 28th International Symposium on Algorithms and Computation (ISAAC 2017), Dagstuhl, Germany: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
Banyassady, B., Korman, M., Mulzer, W., van Renssen, A., Roeloffzen, M., Seiferth, P., Stein, Y. (2017). Improved time-space trade-offs for computin Voronoi diagrams. 34th International Symposium on Theoretical Aspects of Computer Science (STACS 2017), Hannover: Schloss Dagstuhl. [More Information]
Banyassady, B., Chiu, M., Korman, M., Mulzer, W., van Renssen, A., Roeloffzen, M., Seiferth, P., Stein, Y., Vogtenhuber, B., Willert, M. (2017). Routing in polygonal domains. 28th International Symposium on Algorithms and Computation (ISAAC 2017), Dagstuhl, Germany: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
Bose, P., Korman, M., van Renssen, A., Verdonschot, S. (2017). Routing on the Visibility Graph. 28th International Symposium on Algorithms and Computation (ISAAC 2017), Dagstuhl, Germany: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
Demaine, E., Korman, M., van Renssen, A., Roeloffzen, M. (2017). Snipperclips: Cutting Tools into Desired Polygons using Themselves. 29th Canadian Conference on Computational Geometry (CCCG 2017), Ottawa.
Baffier, J., Chiu, M., Diez, Y., Korman, M., Mitsou, V., van Renssen, A., Roeloffzen, M., Uno, Y. (2016). Hanabi is NP-complete, even for cheaters who look at their cards. 8th International Conference on Fun with Algorithms (FUN 2016), La Maddalena: Schloss Dagstuhl - Leibniz Center for Informatics. [More Information]
De Carufel, J., Katz, M., Korman, M., van Renssen, A., Roeloffzen, M., Smorodinsky, S. (2016). On interference among moving sensors and related problems. 24th Annual European Symposium on Algorithms, ESA 2016, Aarhus, Denmark: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
Aichholzer, O., Hackl, T., Korman, M., Pilz, A., Rote, G., van Renssen, A., Roeloffzen, M., Vogtenhuber, B. (2016). Packing short plane spanning trees in complete geometric graphs. 27th International Symposium on Algorithms and Computation (ISAAC 2016), Sydney: Schloss Dagstuhl - Leibniz Center for Informatics. [More Information]
Demaine, E., Korman, M., Ku, J., Mitchell, J., Otachi, Y., van Renssen, A., Roeloffzen, M., Uehara, R., Uno, Y. (2016). Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces. 18th Japan Conference on Discrete and Computational Geometry and Graphs JCDCGG 2015, Cham: Springer Link. [More Information]
Aronov, B., Korman, M., Pratt, S., van Renssen, A., Roeloffzen, M. (2016). Time-space trade-offs for triangulating a simple polygon. 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Reykjavik: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S. (2015). Competitive local routing with constraints. 26th International Symposium on Algorithms and Computation (ISAAC 2015), Nagoya: Springer. [More Information]
Bose, P., De Carufel, J., van Renssen, A. (2015). Constrained Empty-Rectangle Delaunay Graphs. 27th Canadian Conference on Computational Geometry, CCCG 2015, kingston: Queens University.
Korman, M., Mulzer, W., van Renssen, A., Roeloffzen, M., Seiferth, P., Stein, Y. (2015). Time-space trade-offs for triangulations and Voronoi diagrams. WADS 2015: Algorithms and Data Structures Symposium. Springer. [More Information]
Bonichon, N., Bose, P., De Carufel, J., Perkovic, L., van Renssen, A. (2015). Upper and lower bounds for online routing on delaunay triangulations. 23rd European Symposium on Algorithms (ESA 2015), Berlin: Springer Verlag. [More Information]
Barba, L., Bose, P., De Carufel, J., Damian, M., Fagerberg, R., van Renssen, A., Taslakian, P., Verdonschot, S. (2014). Continuous Yao graphs. 26th Canadian Conference on Computational Geometry (CCCG 2014), Halifax: Canadian Conference on Computational Geometry.
Barba, L., Bose, P., Damian, M., Fagerberg, R., Keng, W., O'Rourke, J., van Renssen, A., Taslakian, P., Verdonschot, S., Xia, G. (2014). New and improved spanning ratios for Yao graphs. 30th Annual Symposium on Computational Geometry, SoCG 2014, Kyoto, Japan: Association for Computing Machinery (ACM). [More Information]
van Renssen, A. (2014). On the spanning ratio of constrained yao-graphs. 26th Canadian Conference on Computational Geometry (CCCG 2014), Halifax: Canadian Conference on Computational Geometry.
Bose, P., Morin, P., van Renssen, A. (2014). The price of order. 25th International Symposium, ISAAC 2014, Jeonju, Korea: Springer. [More Information]
Bose, P., van Renssen, A. (2014). Upper bounds on the spanning ratio of constrained theta-graphs. 11th Latin American Theoretical Informatics Symposium (LATIN 2014), Uruguay: Springer Verlag. [More Information]
Bose, P., van Renssen, A., Verdonschot, S. (2013). On the spanning ratio of theta-graphs. 13th International Symposium on Algorithms and Data Structures, London, Canada: Springer. [More Information]
Barba, L., Bose, P., De Carufel, J., van Renssen, A., Verdonschot, S. (2013). On the stretch factor of the theta-4 graph. 13th International Symposium on Algorithms and Data Structures, London, Canada: Springer. [More Information]
Bose, P., Morin, P., van Renssen, A., Verdonschot, S. (2013). The (theta)5-graph is a spanner. 39th International Workshop on Graph-Theoretic Concepts in Computer Science, Lubeck, Germany: Springer Verlag. [More Information]
Aichholzer, O., Bae, S., Barba, L., Bose, P., Korman, M., van Renssen, A., Taslakian, P., Verdonschot, S. (2013). Theta-3 is connected. 25th Canadian Conference on Computational Geometry, Waterloo, Canada: Canadian Conference on Computational Geometry.
Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S. (2012). Competitive routing in the half-Theta 6-graph. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), Kyoto: Association for Computing Machinery (ACM).
Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S. (2012). Competitive routing on a bounded-degree plane spanner. 24th Canadian Conference on Computational Geometry (CCCG 2012), Charlottetown: Elsevier.
Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S. (2012). On plane constrained bounded-degree spanners. 10th Latin American Symposium on Theoretical Informatics (LATIN 2012), Berlin: Springer. [More Information]
Bose, P., De Carufel, J., Morin, P., van Renssen, A., Verdonschot, S. (2012). Optimal bounds on theta-graphs: More is not always better. 24th Canadian Conference on Computational Geometry (CCCG 2012), Charlottetown: Elsevier.
Bose, P., Jansens, D., van Renssen, A., Saumell, M., Verdonschot, S. (2011). Making triangulations 4-connected using flips. 23rd Annual Canadian Conference on Computational Geometry (CCCG 2011), Toronto: Canadian Conference on Computational Geometry.
van Renssen, A., Speckmann, B. (2011). The 2x2 simple packing problem. 23rd Annual Canadian Conference on Computational Geometry (CCCG 2011), Toronto: Canadian Conference on Computational Geometry.
Meulemans, W., van Renssen, A., Speckmann, B. (2010). Area-preserving subdivision schematization. 6th International Conference on Geographic Information Science (GIScience 2010), Zurich: Springer. [More Information]

show 43 more

By Year

Expand all

2023

Aichholzer, O., Korman, M., Okamoto, Y., Parada, I., Perz, D., van Renssen, A., Vogtenhuber, B. (2023). Graphs with large total angular resolution. Theoretical Computer Science, 943, 73-88. [More Information]
Korman, M., van Renssen, A., Roeloffzen, M., Staals, F. (2023). KINETIC GEODESIC VORONOI DIAGRAMS IN A SIMPLE POLYGON. SIAM Journal on Discrete Mathematics, 37(4), 2276-2311. [More Information]

2022

Gudmundsson, J., van de Kerkhof, M., van Renssen, A., Staals, F., Wiratma, L., Wong, S. (2022). Covering a set of line segments with a few squares. Theoretical Computer Science, 923, 74-98. [More Information]
Brankovic, M., Gudmundsson, J., van Renssen, A. (2022). Local routing in a tree metric 1-spanner. Journal of Combinatorial Optimization, 44(4), 2642-2660. [More Information]
Ashvinkumar, V., Gudmundsson, J., Levcopoulos, C., Nilsson, B., van Renssen, A. (2022). Local Routing in Sparse and Lightweight Geometric Graphs. Algorithmica, 84(5), 1316-1340. [More Information]

2021

van Renssen, A., Wong, G. (2021). Bounded-Degree Spanners in the Presence of Polygonal Obstacles. Theoretical Computer Science, 854, 159-173. [More Information]
Bose, P., Korman, M., van Renssen, A., Verdonschot, S. (2021). Constrained routing between non-visible vertices. Theoretical Computer Science, 861, 144-154. [More Information]
Gudmundsson, J., van de Kerkhof, M., van Renssen, A., Staals, F., Wiratma, L., Wong, S. (2021). Covering a Set of Line Segments with a Few Squares. 12th International Conference on Algorithms and Complexity, CIAC 2021, Cham: Springer. [More Information]
Arseneva, E., Chiu, M., Korman, M., Markovic, A., Okamoto, Y., Ooms, A., van Renssen, A., Roeloffzen, M. (2021). Rectilinear link diameter and radius in a rectilinear polygonal domain. Computational Geometry: Theory and Applications, 92, 1-11. [More Information]
Abel, Z., Akitaya, H., Chiu, M., Demaine, E., Demaine, M., Hesterberg, A., Korman, M., Lynch, J., van Renssen, A., Roeloffzen, M. (2021). Snipperclips: Cutting tools into desired polygons using themselves. Computational Geometry: Theory and Applications, 98, 101784. [More Information]
Gudmundsson, J., van Renssen, A., Saeidi, Z., Wong, S. (2021). Translation Invariant Fréchet Distance Queries. Algorithmica, 83(11), 3514-3533. [More Information]
Akitaya, H., Arkin, E., Damian, M., Demaine, E., Dujmovic, V., Flatland, R., Korman, M., Palop, B., Parada, I., van Renssen, A., et al (2021). Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers. Algorithmica, 83(5), 1316-1351. [More Information]

show 4 more

2020

Brankovic, M., Grujic, N., van Renssen, A., Seybold, M. (2020). A simple dynamization of trapezoidal point location in planar subdivisions. 47th International Colloquium on Automata, Languages and Programming (ICALP 2020), Wadern: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
Carmi, P., Chiu, M., Katz, M., Korman, M., Okamoto, Y., van Renssen, A., Roeloffzen, M., Shiitada, T., Smorodinsky, S. (2020). Balanced line separators of unit disk graphs. Computational Geometry: Theory and Applications, 86, 1-14. [More Information]
van Renssen, A., Wong, G. (2020). Bounded-Degree Spanners in the Presence of Polygonal Obstacles. 26th International Computing and Combinatorics Conference (COCOON 2020), Cham: Springer. [More Information]
Korman, M., van Renssen, A., Roeloffzen, M., Staals, F. (2020). Kinetic geodesic Voronoi diagrams in a simple polygon. 47th International Colloquium on Automata, Languages and Programming (ICALP 2020), Wadern: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
Brankovic, M., Gudmundsson, J., van Renssen, A. (2020). Local Routing in a Tree Metric 1-Spanner. 26th International Computing and Combinatorics Conference (COCOON 2020), Cham: Springer. [More Information]
Chiu, M., Cleve, J., Klost, K., Korman, M., Mulzer, W., van Renssen, A., Roeloffzen, M., Willert, M. (2020). Routing in Histograms. 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020), Cham: Springer. [More Information]
Banyassady, B., Chiu, M., Korman, M., Mulzer, W., van Renssen, A., Roeloffzen, M., Seiferth, P., Stein, Y., Vogtenhuber, B., Willert, M. (2020). Routing in Polygonal Domains. Computational Geometry: Theory and Applications, 87, 101593. [More Information]
Demaine, E., Korman, M., Ku, J., Mitchell, J., Otachi, Y., van Renssen, A., Roeloffzen, M., Uehara, R., Uno, Y. (2020). Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces. Computational Geometry: Theory and Applications, 90, 101648. [More Information]

show 5 more

2019

Barba, L., Cardinal, J., Korman, M., Langerman, S., van Renssen, A., Roeloffzen, M., Verdonschot, S. (2019). Dynamic Graph Coloring. Algorithmica, 81(4), 1319-1341. [More Information]
Ahn, H., Bae, S., Choi, J., Korman, M., Mulzer, W., Oh, E., Park, J., van Renssen, A., Vigneron, A. (2019). Faster Algorithms for Growing Prioritized Disks and Rectangles. Computational Geometry: Theory and Applications, 80, 23-39. [More Information]
de Berg, M., Leijsen, T., Markovic, A., van Renssen, A., Roeloffzen, M., Woeginger, G. (2019). Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points. International Journal of Computational Geometry and Applications, 29(1), 49-72. [More Information]
Kraaijer, R., van Kreveld, M., Meulemans, W., van Renssen, A. (2019). Geometry and Generation of a New Graph Planarity Game. Journal of Graph Algorithms and Applications, 23(4), 603-624. [More Information]
Aichholzer, O., Korman, M., Okamoto, Y., Parada, I., Perz, D., van Renssen, A., Vogtenhuber, B. (2019). Graphs with Large Total Angular Resolution. 27th International Symposium on Graph Drawing and Network Visualization (GD 2019), Cham: Springer. [More Information]
Ashvinkumar, V., Gudmundsson, J., Levcopoulos, C., Nilsson, B., van Renssen, A. (2019). Local Routing in Sparse and Lightweight Geometric Graphs. 30th International Symposium on Algorithms and Computation (ISAAC 2019), Saarbrucken/Wadern: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S. (2019). On Plane Constrained Bounded-Degree Spanners. Algorithmica, 81(4), 1392-1415. [More Information]
Aichholzer, O., Hackl, T., Korman, M., Pilz, A., van Renssen, A., Roeloffzen, M., Rote, G., Vogtenhuber, B. (2019). Packing Plane Spanning Graphs with Short Edges in Complete Geometric Graphs. Computational Geometry: Theory and Applications, 82, 1-15. [More Information]
Bose, P., van Renssen, A. (2019). Spanning Properties of Yao and Theta-Graphs in the Presence of Constraints. International Journal of Computational Geometry and Applications, 29(2), 95-120. [More Information]
Akitaya, H., Arkin, E., Damian, M., Demaine, E., Dujmovic, V., Flatland, R., Korman, M., Palop, B., Parada, I., van Renssen, A., et al (2019). Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers. 27th Annual European Symposium on Algorithms (ESA 2019), Munich: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. [More Information]

show 7 more

2018

Bose, P., De Carufel, J., van Renssen, A. (2018). Constrained generalized Delaunay graphs are plane spanners. Computational Geometry: Theory and Applications, 74, 50-65. [More Information]
Bakhshesh, D., Barba, L., Bose, P., De Carufel, J., Damian, M., Fagerberg, R., Farshi, M., van Renssen, A., Taslakian, P., Verdonschot, S. (2018). Continuous Yao graphs. Computational Geometry: Theory and Applications, 67, 42-52. [More Information]
Kraaijer, R., van Kreveld, M., Meulemans, W., van Renssen, A. (2018). Geometry and Generation of a new Graph Planarity Game. IEEE Conference on Computational Intelligence and Games (CIG 2018), Maastricht: IEEE Computer Society. [More Information]
Banyassady, B., Korman, M., Mulzer, W., van Renssen, A., Roeloffzen, M., Seiferth, P., Stein, Y. (2018). Improved Time-Space Trade-offs for Computing Voronoi Diagrams. Journal of Computational Geometry, 9(1), 191-212.
Arseneva, E., Chiu, M., Korman, M., Markovic, A., Okamoto, Y., Ooms, A., van Renssen, A., Roeloffzen, M. (2018). Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain. 29th International Symposium on Algorithms and Computation (ISAAC 2018), Germany: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
Bose, P., Korman, M., van Renssen, A., Verdonschot, S. (2018). Routing on the Visibility Graph. Journal of Computational Geometry, 9(1), 430-453. [More Information]
Korman, M., Mulzer, W., van Renssen, A., Roeloffzen, M., Seiferth, P., Stein, Y. (2018). Time-Space Trade-offs for Triangulations and Voronoi Diagrams. Computational Geometry: Theory and Applications, 73, 35-45. [More Information]

show 4 more

2017

Carmi, P., Chiu, M., Katz, M., Korman, M., Okamoto, Y., van Renssen, A., Roeloffzen, M., Shiitada, T., Smorodinsky, S. (2017). Balanced line separators of unit disk graphs. 15th International Symposium on Algorithms and Data Structures (WADS 2017), Cham: Springer International Publishing. [More Information]
Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S. (2017). Competitive Local Routing with Constraints. Journal of Computational Geometry, 8(1), 125-152. [More Information]
Bose, P., De Carufel, J., van Renssen, A. (2017). Constrained generalized Delaunay graphs are plane spanners. International Conference on Computational Intelligence in Information Systems (CIIS 2016), Cham: Springer. [More Information]
Bose, P., Korman, M., van Renssen, A., Verdonschot, S. (2017). Constrained routing between non-visible vertices. 23rd International Conference on Computing and Combinatorics (COCOON 2017), Hong Kong: Springer. [More Information]
Barba, L., Cardinal, J., Korman, M., Langerman, S., van Renssen, A., Roeloffzen, M., Verdonschot, S. (2017). Dynamic graph coloring. 15th International Symposium on Algorithms and Data Structures (WADS 2017), Cham: Springer International Publishing. [More Information]
Ahn, H., Bae, S., Choi, J., Korman, M., Mulzer, W., Oh, E., Park, J., van Renssen, A., Vigneron, A. (2017). Faster algorithms for growing prioritized disks and rectangles. 28th International Symposium on Algorithms and Computation (ISAAC 2017), Dagstuhl, Germany: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
de Berg, M., Leijsen, T., Merkovic, A., van Renssen, A., Roeloffzen, M., Woeginger, G. (2017). Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points. 28th International Symposium on Algorithms and Computation (ISAAC 2017), Dagstuhl, Germany: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
Baffier, J., Chiu, M., Diez, Y., Korman, M., Mitsou, V., van Renssen, A., Roeloffzen, M., Uno, Y. (2017). Hanabi is NP-hard, even for cheaters who look at their cards. Theoretical Computer Science, 675, 43-55. [More Information]
Banyassady, B., Korman, M., Mulzer, W., van Renssen, A., Roeloffzen, M., Seiferth, P., Stein, Y. (2017). Improved time-space trade-offs for computin Voronoi diagrams. 34th International Symposium on Theoretical Aspects of Computer Science (STACS 2017), Hannover: Schloss Dagstuhl. [More Information]
De Carufel, J., Katz, M., Korman, M., van Renssen, A., Roeloffzen, M., Smorodinsky, S. (2017). On interference among moving sensors and related problems. Journal of Computational Geometry, 8(1), 32-46. [More Information]
Banyassady, B., Chiu, M., Korman, M., Mulzer, W., van Renssen, A., Roeloffzen, M., Seiferth, P., Stein, Y., Vogtenhuber, B., Willert, M. (2017). Routing in polygonal domains. 28th International Symposium on Algorithms and Computation (ISAAC 2017), Dagstuhl, Germany: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
Bose, P., Korman, M., van Renssen, A., Verdonschot, S. (2017). Routing on the Visibility Graph. 28th International Symposium on Algorithms and Computation (ISAAC 2017), Dagstuhl, Germany: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
Demaine, E., Korman, M., van Renssen, A., Roeloffzen, M. (2017). Snipperclips: Cutting Tools into Desired Polygons using Themselves. 29th Canadian Conference on Computational Geometry (CCCG 2017), Ottawa.
Aronov, B., Korman, M., Pratt, S., van Renssen, A., Roeloffzen, M. (2017). Time-Space Trade-offs for Triangulating a Simple Polygon. Journal of Computational Geometry, 8(1), 105-124. [More Information]
Bonichon, N., Bose, P., De Carufel, J., Perkovic, L., van Renssen, A. (2017). Upper and Lower Bounds for Online Routing on Delaunay Triangulations. Discrete and Computational Geometry, 58(2), 482-504. [More Information]

show 12 more

2016

Buchin, K., Meulemans, W., van Renssen, A., Speckmann, B. (2016). Area-Preserving Simplification and Schematization of Polygonal Subdivisions. ACM Transactions on Spatial Algorithms and Systems, 2(1), 2. [More Information]
Baffier, J., Chiu, M., Diez, Y., Korman, M., Mitsou, V., van Renssen, A., Roeloffzen, M., Uno, Y. (2016). Hanabi is NP-complete, even for cheaters who look at their cards. 8th International Conference on Fun with Algorithms (FUN 2016), La Maddalena: Schloss Dagstuhl - Leibniz Center for Informatics. [More Information]
De Carufel, J., Katz, M., Korman, M., van Renssen, A., Roeloffzen, M., Smorodinsky, S. (2016). On interference among moving sensors and related problems. 24th Annual European Symposium on Algorithms, ESA 2016, Aarhus, Denmark: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
Aichholzer, O., Hackl, T., Korman, M., Pilz, A., Rote, G., van Renssen, A., Roeloffzen, M., Vogtenhuber, B. (2016). Packing short plane spanning trees in complete geometric graphs. 27th International Symposium on Algorithms and Computation (ISAAC 2016), Sydney: Schloss Dagstuhl - Leibniz Center for Informatics. [More Information]
Demaine, E., Korman, M., Ku, J., Mitchell, J., Otachi, Y., van Renssen, A., Roeloffzen, M., Uehara, R., Uno, Y. (2016). Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces. 18th Japan Conference on Discrete and Computational Geometry and Graphs JCDCGG 2015, Cham: Springer Link. [More Information]
Bose, P., Morin, P., van Renssen, A. (2016). The Price of Order. International Journal of Computational Geometry and Applications, 26(43193), 135-149. [More Information]
Aronov, B., Korman, M., Pratt, S., van Renssen, A., Roeloffzen, M. (2016). Time-space trade-offs for triangulating a simple polygon. 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Reykjavik: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
Bose, P., De Carufel, J., Morin, P., van Renssen, A., Verdonschot, S. (2016). Towards tight bounds on theta-graphs: More is not always better. Theoretical Computer Science, 616, 70-93. [More Information]

show 5 more

2015

Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S. (2015). Competitive local routing with constraints. 26th International Symposium on Algorithms and Computation (ISAAC 2015), Nagoya: Springer. [More Information]
Bose, P., De Carufel, J., van Renssen, A. (2015). Constrained Empty-Rectangle Delaunay Graphs. 27th Canadian Conference on Computational Geometry, CCCG 2015, kingston: Queens University.
Barba, L., Bose, P., Damian, M., Fagerberg, R., Keng, W., O'Rourke, J., van Renssen, A., Taslakian, P., Verdonschot, S., Xia, G. (2015). New and Improved Spanning Ratios for Yao Graphs. Journal of Computational Geometry, 6(2), 19-53.
Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S. (2015). Optimal local routing on Delaunay triangulations defined by empty equilateral triangles. SIAM Journal on Computing, 44(6), 1626-1649. [More Information]
Aichholzer, O., Bae, S., Barba, L., Bose, P., Korman, M., van Renssen, A., Taslakian, P., Verdonschot, S. (2015). Reprint of: Theta-3 is connected. Computational Geometry: Theory and Applications, 48(5), 407-414. [More Information]
Bose, P., Morin, P., van Renssen, A., Verdonschot, S. (2015). The Theta-5-graph is a spanner. Computational Geometry: Theory and Applications, 48(2), 108-119. [More Information]
Korman, M., Mulzer, W., van Renssen, A., Roeloffzen, M., Seiferth, P., Stein, Y. (2015). Time-space trade-offs for triangulations and Voronoi diagrams. WADS 2015: Algorithms and Data Structures Symposium. Springer. [More Information]
Bonichon, N., Bose, P., De Carufel, J., Perkovic, L., van Renssen, A. (2015). Upper and lower bounds for online routing on delaunay triangulations. 23rd European Symposium on Algorithms (ESA 2015), Berlin: Springer Verlag. [More Information]

show 5 more

2014

Barba, L., Bose, P., De Carufel, J., Damian, M., Fagerberg, R., van Renssen, A., Taslakian, P., Verdonschot, S. (2014). Continuous Yao graphs. 26th Canadian Conference on Computational Geometry (CCCG 2014), Halifax: Canadian Conference on Computational Geometry.
Bose, P., Jansens, D., van Renssen, A., Saumell, M., Verdonschot, S. (2014). Making triangulations 4-connected using flips. Computational Geometry: Theory and Applications, 47(2), 187-197. [More Information]
Barba, L., Bose, P., Damian, M., Fagerberg, R., Keng, W., O'Rourke, J., van Renssen, A., Taslakian, P., Verdonschot, S., Xia, G. (2014). New and improved spanning ratios for Yao graphs. 30th Annual Symposium on Computational Geometry, SoCG 2014, Kyoto, Japan: Association for Computing Machinery (ACM). [More Information]
van Renssen, A. (2014). On the spanning ratio of constrained yao-graphs. 26th Canadian Conference on Computational Geometry (CCCG 2014), Halifax: Canadian Conference on Computational Geometry.
Bose, P., Morin, P., van Renssen, A. (2014). The price of order. 25th International Symposium, ISAAC 2014, Jeonju, Korea: Springer. [More Information]
Aichholzer, O., Bae, S., Barba, L., Bose, P., Korman, M., van Renssen, A., Taslakian, P., Verdonschot, S. (2014). Theta-3 is connected. Computational Geometry: Theory and Applications, 47(9), 910-917. [More Information]
Bose, P., van Renssen, A. (2014). Upper bounds on the spanning ratio of constrained theta-graphs. 11th Latin American Theoretical Informatics Symposium (LATIN 2014), Uruguay: Springer Verlag. [More Information]

show 4 more

2013

Bose, P., van Renssen, A., Verdonschot, S. (2013). On the spanning ratio of theta-graphs. 13th International Symposium on Algorithms and Data Structures, London, Canada: Springer. [More Information]
Barba, L., Bose, P., De Carufel, J., van Renssen, A., Verdonschot, S. (2013). On the stretch factor of the theta-4 graph. 13th International Symposium on Algorithms and Data Structures, London, Canada: Springer. [More Information]
Bose, P., Morin, P., van Renssen, A., Verdonschot, S. (2013). The (theta)5-graph is a spanner. 39th International Workshop on Graph-Theoretic Concepts in Computer Science, Lubeck, Germany: Springer Verlag. [More Information]
Aichholzer, O., Bae, S., Barba, L., Bose, P., Korman, M., van Renssen, A., Taslakian, P., Verdonschot, S. (2013). Theta-3 is connected. 25th Canadian Conference on Computational Geometry, Waterloo, Canada: Canadian Conference on Computational Geometry.

show 1 more

2012

Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S. (2012). Competitive routing in the half-Theta 6-graph. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), Kyoto: Association for Computing Machinery (ACM).
Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S. (2012). Competitive routing on a bounded-degree plane spanner. 24th Canadian Conference on Computational Geometry (CCCG 2012), Charlottetown: Elsevier.
Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S. (2012). On plane constrained bounded-degree spanners. 10th Latin American Symposium on Theoretical Informatics (LATIN 2012), Berlin: Springer. [More Information]
Bose, P., De Carufel, J., Morin, P., van Renssen, A., Verdonschot, S. (2012). Optimal bounds on theta-graphs: More is not always better. 24th Canadian Conference on Computational Geometry (CCCG 2012), Charlottetown: Elsevier.

show 1 more

2011

Bose, P., Jansens, D., van Renssen, A., Saumell, M., Verdonschot, S. (2011). Making triangulations 4-connected using flips. 23rd Annual Canadian Conference on Computational Geometry (CCCG 2011), Toronto: Canadian Conference on Computational Geometry.
van Renssen, A., Speckmann, B. (2011). The 2x2 simple packing problem. 23rd Annual Canadian Conference on Computational Geometry (CCCG 2011), Toronto: Canadian Conference on Computational Geometry.

2010

Meulemans, W., van Renssen, A., Speckmann, B. (2010). Area-preserving subdivision schematization. 6th International Conference on Geographic Information Science (GIScience 2010), Zurich: Springer. [More Information]

Selected Grants

2024

Algorithms for Future-Proof Networks, Gudmundsson J, van Renssen A, Umboh S, Umboh S, Berg M, Australian Research Council (ARC)/Discovery Projects (DP)

International collaboration

Carleton University [Canada]

Prof. Prosenjit Bose
Computational Geometry Lab, School of Computer Science

Faculty of Engineering

Page not found

Dr Andre van Renssen

FOR Codes

Publications

By Type

By Year

Selected Grants

2024

International collaboration