André van Renssen
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
André van Renssen has a total of 143 co-authors. Here are the top co-authors by number of shared publications:
- Prosenjit Bose
School of Computer Science, Carleton University, Ottawa, Canada
33 shared publications Sander Verdonschot
15 shared publicationsMatias Korman
Siemens Electronic Design Automation, Wilsonville, OR 97070 USA
13 shared publications- Sander Verdonschot
School of Electrical Engineering and Computer Science University of Ottawa Canada
13 shared publications - Marcel Roeloffzen
Dept. of Mathematics and Computer Science TU Eindhoven Eindhoven The Netherlands
11 shared publications - Joachim Gudmundsson
University of Sydney, Sydney, Australia
10 shared publications
Latest Publications
- Open Access
- 12 August 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1085
Local routing on ordered Θ-graphs
- 12 August 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1085
Open AccessLocal routing on ordered Θ-graphs
- Open Access
- 9 January 2026
- Published by Elsevier in Transportation Research Part C: Emerging Technologies
- Vol. 184
Dynamic on-demand delivery with spatial divisions of labor
- 9 January 2026
- Published by Elsevier in Transportation Research Part C: Emerging Technologies
- Vol. 184
Open AccessDynamic on-demand delivery with spatial divisions of labor
- Open Access
- 11 December 2025
- Published by Springer Nature in Algorithmica
- Vol. 88 (1) , 14
Oriented Spanners
Given a point set P in the Euclidean plane and a parameter t , we define an oriented t -spanner G as an oriented subgraph of the complete bi-directed graph such that for every pair of points, the shortest closed walk in G through those points is at most a factor t longer than the shortest cycle in the complete graph on P . We investigate the problem of computing sparse graphs with small oriented dilation. As we can show that minimising oriented dilation for a given number of edges is NP-hard in the plane, we first consider one-dimensional point sets. While obtaining a 1-spanner in this setting is straightforward, already for five points such a spanner has no plane embedding with the leftmost and rightmost point on the outer face. This leads to restricting to oriented graphs with a one-page book embedding on the one-dimensional point set. For this case we present a dynamic program to compute the graph of minimum oriented dilation that runs in $$\mathcal {O}(n^7)$$ time for n points, and a greedy algorithm that computes a 5-spanner in $$\mathcal {O}(n\log n)$$ time. Expanding these results finally gives us a result for two-dimensional point sets: we prove that for convex point sets the greedy triangulation results in a plane oriented t -spanner with $$t=7.2 \cdot t_g$$ , where $$t_g$$ is an upper bound on the dilation of the greedy triangulation.- 11 December 2025
- Published by Springer Nature in Algorithmica
- Vol. 88 (1) , 14
Open AccessOriented Spanners
Given a point set P in the Euclidean plane and a parameter t , we define an oriented t -spanner G as an oriented subgraph of the complete bi-directed graph such that for every pair of points, the shortest closed walk in G through those points is at most a factor t longer than the shortest cycle in the complete graph on P . We investigate the problem of computing sparse graphs with small oriented dilation. As we can show that minimising oriented dilation for a given number of edges is NP-hard in the plane, we first consider one-dimensional point sets. While obtaining a 1-spanner in this setting is straightforward, already for five points such a spanner has no plane embedding with the leftmost and rightmost point on the outer face. This leads to restricting to oriented graphs with a one-page book embedding on the one-dimensional point set. For this case we present a dynamic program to compute the graph of minimum oriented dilation that runs in $$\mathcal {O}(n^7)$$ time for n points, and a greedy algorithm that computes a 5-spanner in $$\mathcal {O}(n\log n)$$ time. Expanding these results finally gives us a result for two-dimensional point sets: we prove that for convex point sets the greedy triangulation results in a plane oriented t -spanner with $$t=7.2 \cdot t_g$$ , where $$t_g$$ is an upper bound on the dilation of the greedy triangulation. - 20 June 2025
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 35 (01n02) , 41-50
Shortest Paths of Mutually Visible Robots
Given a set of [ ] point robots inside a simple polygon [ ], the task is to move the robots from their starting positions to their target positions along their shortest paths, while the mutual visibility of these robots is preserved. Previous work only considered two robots. In this paper, we present an [ ] time algorithm, where [ ] is the complexity of the polygon, when all the starting positions lie on a line segment [ ], all the target positions lie on a line segment [ ], and [ ] and [ ] do not intersect. We also argue that there is no polynomial-time algorithm, whose running time depends only on [ ] and [ ], that uses a single strategy for the case where [ ] and [ ] intersect.
- 20 June 2025
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 35 (01n02) , 41-50
Shortest Paths of Mutually Visible Robots
Given a set of [ ] point robots inside a simple polygon [ ], the task is to move the robots from their starting positions to their target positions along their shortest paths, while the mutual visibility of these robots is preserved. Previous work only considered two robots. In this paper, we present an [ ] time algorithm, where [ ] is the complexity of the polygon, when all the starting positions lie on a line segment [ ], all the target positions lie on a line segment [ ], and [ ] and [ ] do not intersect. We also argue that there is no polynomial-time algorithm, whose running time depends only on [ ] and [ ], that uses a single strategy for the case where [ ] and [ ] intersect.
- Open Access
- 16 April 2025
- Published by Springer Nature in Algorithmica
- Vol. 87 (7) , 1060-1080
The Tight Spanning Ratio of the Rectangle Delaunay Triangulation
Spanner construction is a well-studied problem and Delaunay triangulations are among the most popular spanners. Tight bounds are known if the Delaunay triangulation is constructed using an equilateral triangle, a square, or a regular hexagon. However, all other shapes have remained elusive. In this paper, we extend the restricted class of spanners for which tight bounds are known. We prove that Delaunay triangulations constructed using rectangles with aspect ratio $$A$$ have spanning ratio at most $$\sqrt{2} \sqrt{1+A^2 + A\sqrt{A^2 + 1}}$$ , which matches the known lower bound.- 16 April 2025
- Published by Springer Nature in Algorithmica
- Vol. 87 (7) , 1060-1080
Open AccessThe Tight Spanning Ratio of the Rectangle Delaunay Triangulation
Spanner construction is a well-studied problem and Delaunay triangulations are among the most popular spanners. Tight bounds are known if the Delaunay triangulation is constructed using an equilateral triangle, a square, or a regular hexagon. However, all other shapes have remained elusive. In this paper, we extend the restricted class of spanners for which tight bounds are known. We prove that Delaunay triangulations constructed using rectangles with aspect ratio $$A$$ have spanning ratio at most $$\sqrt{2} \sqrt{1+A^2 + A\sqrt{A^2 + 1}}$$ , which matches the known lower bound. - Open Access
- 19 March 2025
- Published by Elsevier in Computational Geometry
- Vol. 129
Pattern formation for fat robots with memory
- 19 March 2025
- Published by Elsevier in Computational Geometry
- Vol. 129
Open AccessPattern formation for fat robots with memory
- Open Access
- 27 December 2024
- Published by Elsevier in Computational Geometry
- Vol. 128
Pattern formation for fat robots with lights
- 27 December 2024
- Published by Elsevier in Computational Geometry
- Vol. 128
Open AccessPattern formation for fat robots with lights
- Open Access
- 29 January 2024
- Published by Association for Computing Machinery (ACM)
- p. 164-171
Designing Problem Sessions for Algorithmic Subjects to Boost Student Confidence
In this paper, we describe how we changed the structure of problem sessions in an algorithmic subject, in order to improve student confidence. The subject in question is taught to very large cohorts of (around 900) students, though our approach can be applied more broadly. We reflect on our experiences over a number of years, including during the pandemic, and show that by adding clear sectioning indicating the style of the questions and by including simple warm-up questions, student engagement and confidence improves, while making the teaching activities of our teaching assistants easier to manage.
- 29 January 2024
- Published by Association for Computing Machinery (ACM)
- p. 164-171
Open AccessDesigning Problem Sessions for Algorithmic Subjects to Boost Student Confidence
In this paper, we describe how we changed the structure of problem sessions in an algorithmic subject, in order to improve student confidence. The subject in question is taught to very large cohorts of (around 900) students, though our approach can be applied more broadly. We reflect on our experiences over a number of years, including during the pandemic, and show that by adding clear sectioning indicating the style of the questions and by including simple warm-up questions, student engagement and confidence improves, while making the teaching activities of our teaching assistants easier to manage.
- Open Access
Generalized Sweeping Line Spanners
We present sweeping line graphs, a generalization of $\Theta$-graphs. We show that these graphs are spanners of the complete graph, as well as of the visibility graph when line segment constraints or polygonal obstacles are considered. Our proofs use general inductive arguments to make the step to the constrained setting. These same arguments could apply to other spanner constructions in the unconstrained setting, removing the need to find separate proofs that they are spanning in the constrained and polygonal obstacle settings.
Open AccessGeneralized Sweeping Line Spanners
We present sweeping line graphs, a generalization of $\Theta$-graphs. We show that these graphs are spanners of the complete graph, as well as of the visibility graph when line segment constraints or polygonal obstacles are considered. Our proofs use general inductive arguments to make the step to the constrained setting. These same arguments could apply to other spanner constructions in the unconstrained setting, removing the need to find separate proofs that they are spanning in the constrained and polygonal obstacle settings.
- 12 October 2023
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 37 (4) , 2276-2311
Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
We study the geodesic Voronoi diagram of a set [Formula: see text] of [Formula: see text] linearly moving sites inside a static simple polygon [Formula: see text] with [Formula: see text] vertices. We identify all events where the structure of the Voronoi diagram changes, bound the number of such events, and then develop a kinetic data structure (KDS) that maintains the geodesic Voronoi diagram as the sites move. To this end, we first analyze how often a single bisector, defined by two sites, or a single Voronoi center, defined by three sites, can change. For both these structures we prove that the number of such changes is at most [Formula: see text], and that this is tight in the worst case. Moreover, we develop compact, responsive, local, and efficient KDSs for both structures. Our data structures use linear space and process a worst-case optimal number of events. Our bisector and Voronoi center KDSs handle each event in [Formula: see text] time. Both structures can be extended to efficiently support updating the movement of the sites as well. Using these data structures as building blocks, we obtain a compact KDS for maintaining the full geodesic Voronoi diagram.
- 12 October 2023
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 37 (4) , 2276-2311
Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
We study the geodesic Voronoi diagram of a set [Formula: see text] of [Formula: see text] linearly moving sites inside a static simple polygon [Formula: see text] with [Formula: see text] vertices. We identify all events where the structure of the Voronoi diagram changes, bound the number of such events, and then develop a kinetic data structure (KDS) that maintains the geodesic Voronoi diagram as the sites move. To this end, we first analyze how often a single bisector, defined by two sites, or a single Voronoi center, defined by three sites, can change. For both these structures we prove that the number of such changes is at most [Formula: see text], and that this is tight in the worst case. Moreover, we develop compact, responsive, local, and efficient KDSs for both structures. Our data structures use linear space and process a worst-case optimal number of events. Our bisector and Voronoi center KDSs handle each event in [Formula: see text] time. Both structures can be extended to efficiently support updating the movement of the sites as well. Using these data structures as building blocks, we obtain a compact KDS for maintaining the full geodesic Voronoi diagram.