About Dr Andre vanRenssen

I’m highly interested in geometric problems (focussing on designing efficient algorithms) and geometric networks, especially in the presence of obstacles.

I have worked on a large variety of geometric and graph-theoretical problems, including geometric network design and routing algorithms, limited memory algorithms, graph colouring and computing shortest paths in polygons.

Through a number of ongoing international research collaborations, we have significantly expanded the knowledge about routing in geometric networks in the presence of obstacles. We have shown when efficient routing algorithms can and cannot be obtained, as well as provided such routing algorithms whenever possible (covering a wide range of geometric properties).

There are a lot of interesting problems in the area of geometric algorithms and networks, regardless of if you want to approach this from a theory-focused or an implementation-focused angle.

Selected publications

• On Plane Constrained Bounded-Degree Spanners, P. Bose, R. Fagerberg, A. van Renssen, and S. Verdonschot. To appear in Algorithmica, 2018.
• Dynamic Graph Coloring, L. Barba, J. Cardinal, M. Korman, S. Langerman, A. van Renssen, M. Roeloffzen, and S. Verdonschot. To appear in Algorithmica, 2018.
• Improved Time-Space Trade-offs for Computing Voronoi Diagrams, B. Banyassady, M. Korman, W. Mulzer, A. van Renssen, M. Roeloffzen, P. Seiferth, and Y. Stein. Journal of Computational Geometry (JoCG), 9(1):191–212, 2018.
• Upper and Lower Bounds for Online Routing on Delaunay Triangulations, N. Bonichon, P. Bose, J.-L. De Carufel, L. Perković, and A. van Renssen. Discrete & Computational Geometry (DCG), 58(2):482–504, 2017.
• Competitive Local Routing with Constraints, P. Bose, R. Fagerberg, A. van Renssen, and S. Verdonschot. Journal of Computational Geometry (JoCG), 8(1):125–152, 2017.
• The Price of Order, P. Bose, P. Morin, and A. van Renssen. International Journal of Computational Geometry & Applications (IJCGA) special issue of ISAAC 2014, 26(03n04):135–149, 2017.• Area-Preserving Simplification and Schematization of Polygonal Subdivisions, K. Buchin, W. Meulemans, A. van Renssen, and B. Speckmann. ACM Transactions on Spatial Algorithms and Systems (ACM TSAS), 2(1):2:1–2:36, 2016.
• Towards Tight Bounds on Theta-Graphs: More is not Always Better, P. Bose, J.-L. De Carufel, P. Morin, A. van Renssen, and S. Verdonschot. Theoretical Computer Science (TCS), 616:70–93, 2016.
• Optimal local routing on Delaunay triangulations defined by empty equilateral triangles, P. Bose, R. Fagerberg, A. van Renssen, and S. Verdonschot. SIAM Journal on Computing (SICOMP), 44(6):1626–1649, 2015.
• New and Improved Spanning Ratios for Yao Graphs, L. Barba, P. Bose, M. Damian, R. Fagerberg, W. L. Keng, J. O’Rourke, A. van Renssen, P. Taslakian, S. Verdonschot, and G. Xia.