12 citations · 48 across the 27 of their papers we have counts for
41 papers
Local Routing on Ordered -graphs
André van Renssen, Shuei Sakaguchi
The problem of locally routing on geometric networks using limited memory is extensively studied in computational geometry. We consider one particular graph, the ordered -graph,…
Spanner for the weighted region problem
Joachim Gudmundsson, Zijin Huang, André van Renssen +1
We consider the problem of computing an approximate weighted shortest path in a weighted subdivision, with weights assigned from the set . We present a data struc…
Designing Problem Sessions for Algorithmic Subjects to Boost Student Confidence
André van Renssen
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…
Shortest Paths of Mutually Visible Robots
Rusul J. Alsaedi, Joachim Gudmundsson, André van Renssen
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, whil…
Pattern Formation for Fat Robots with Memory
Rusul J. Alsaedi, Joachim Gudmundsson, André van Renssen
Given a set of autonomous, anonymous, indistinguishable, silent, and possibly disoriented mobile unit disk (i.e., fat) robots operating following Look-Compute-Move cycles…
Computing a Subtrajectory Cluster from c-packed Trajectories
Joachim Gudmundsson, Zijin Huang, André van Renssen +1
We present a near-linear time approximation algorithm for the subtrajectory cluster problem of -packed trajectories. The problem involves finding subtrajectories within a gi…
Oriented Spanners
Kevin Buchin, Joachim Gudmundsson, Antonia Kalb +4
Given a point set in the Euclidean plane and a parameter , we define an \emph{oriented -spanner} as an oriented subgraph of the complete bi-directed graph such that f…
Pattern Formation for Fat Robots with Lights
Rusul J. Alsaedi, Joachim Gudmundsson, André van Renssen
Given a set of unit disk robots in the Euclidean plane, we consider the Pattern Formation problem, i.e., the robots must reposition themselves to form a given target patt…
The Tight Spanning Ratio of the Rectangle Delaunay Triangulation
Andrè van Renssen, Yuan Sha, Yucheng Sun +1
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…
The Mutual Visibility Problem for Fat Robots with Lights
Rusul J. Alsaedi, Joachim Gudmundsson, André van Renssen
Given a set of unit disk robots in the Euclidean plane, we consider the fundamental problem of providing mutual visibility to them: the robots must reposition themselves…
Generalized Sweeping Line Spanners
Keenan Lee, André van Renssen
We present sweeping line graphs, a generalization of -graphs. We show that these graphs are spanners of the complete graph, as well as of the visibility graph when line segment…
Covering a set of line segments with a few squares
Joachim Gudmundsson, Mees van de Kerkhof, André van Renssen +3
We study three covering problems in the plane. Our original motivation for these problems come from trajectory analysis. The first is to decide whether a given set of line segments…
Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
Matias Korman, André van Renssen, Marcel Roeloffzen +1
We study the geodesic Voronoi diagram of a set of linearly moving sites inside a static simple polygon with vertices. We identify all events where the structure of…
Local Routing in Sparse and Lightweight Geometric Graphs
Vikrant Ashvinkumar, Joachim Gudmundsson, Christos Levcopoulos +2
Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no -competitive online r…
Graphs with large total angular resolution
Oswin Aichholzer, Matias Korman, Yoshio Okamoto +4
The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawi…
Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain
Elena Arseneva, Man-Kwun Chiu, Matias Korman +5
We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of vertices and holes. We introduce a \emph{gr…
Constrained Routing Between Non-Visible Vertices
Prosenjit Bose, Matias Korman, André van Renssen +1
In this paper we study local routing strategies on geometric graphs. Such strategies use geometric properties of the graph like the coordinates of the current and target nodes to r…
Balanced Line Separators of Unit Disk Graphs
Paz Carmi, Man Kwun Chiu, Matthew J. Katz +6
We prove a geometric version of the graph separator theorem for the unit disk intersection graph: for any set of unit disks in the plane there exists a line such that $\…
Dynamic Graph Coloring
Luis Barba, Jean Cardinal, Matias Korman +4
In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a graph under insertion and deletion of vertice…
Improved Time-Space Trade-offs for Computing Voronoi Diagrams
Bahareh Banyassady, Matias Korman, Wolfgang Mulzer +4
Let be a planar set of sites in general position. For , the Voronoi diagram of order for is obtained by subdividing the plane into cells such t…
Faster Algorithms for Growing Prioritized Disks and Rectangles
Hee-Kap Ahn, Sang Won Bae, Jongmin Choi +6
Motivated by map labeling, Funke, Krumpe, and Storandt [IWOCA 2016] introduced the following problem: we are given a sequence of disks in the plane. Initially, all disks have r…
On Plane Constrained Bounded-Degree Spanners
Prosenjit Bose, Rolf Fagerberg, André van Renssen +1
Let be a finite set of points in the plane and a set of non-crossing line segments with endpoints in . The visibility graph of with respect to , denoted $Vis(P,S)…
Routing in Polygonal Domains
Bahareh Banyassady, Man-Kwun Chiu, Matias Korman +7
We consider the problem of routing a data packet through the visibility graph of a polygonal domain with vertices and holes. We may preprocess to obtain a label and…
Packing Short Plane Spanning Graphs in Complete Geometric Graphs
Oswin Aichholzer, Thomas Hackl, Matias Korman +5
Given a set of points in the plane, we want to establish a connection network between these points that consists of several disjoint layers. Motivated by sensor networks, we want t…