12 citations · 48 across the 27 of their papers we have counts for
11 papers · 1 filter
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…
Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces
Erik D. Demaine, Matias Korman, Jason S. Ku +6
We study the complexity of symmetric assembly puzzles: given a collection of simple polygons, can we translate, rotate, and possibly flip them so that their interior-disjoint union…
Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points
Mark de Berg, Tim Leijsen, André van Renssen +3
We introduce the fully-dynamic conflict-free coloring problem for a set of intervals in with respect to points, where the goal is to maintain a conflict-free col…