7 citations · 24 across the 10 of their papers we have counts for
10 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…
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 $\…
Line Segment Covering of Cells in Arrangements
Matias Korman, Sheung-Hung Poon, Marcel Roeloffzen
Given a collection of line segments, we consider its arrangement and study the problem of covering all cells with line segments of . That is, we want to find a minimum-size…
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…
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…
Faster DB-scan and HDB-scan in Low-Dimensional Euclidean Spaces
Mark de Berg, Ade Gunawan, Marcel Roeloffzen
We present a new algorithm for the widely used density-based clustering method DBscan. Our algorithm computes the DBscan-clustering in time in , irrespec…
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…