193 citations · 258 across the 23 of their papers we have counts for
27 papers
Geometric Spanning Trees Minimizing the Wiener Index
A. Karim Abu-Affash, Paz Carmi, Ori Luwisch +1
The Wiener index of a network, introduced by the chemist Harry Wiener, is the sum of distances between all pairs of nodes in the network. This index, originally used in chemical gr…
Minimum-link -Oriented Paths Visiting a Sequence of Regions in the Plane
Kerem Geva, Matthew J. Katz, Joseph S. B. Mitchell +1
Let be a set of -oriented disjoint segments in the plane, where is a given finite set of orientations that spans the plane, and let and be two…
Area-Optimal Simple Polygonalizations: The CG Challenge 2019
Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich +2
We give an overview of theoretical and practical aspects of finding a simple polygon of minimum (Min-Area) or maximum (Max-Area) possible area for a given set of n points in the pl…
Shortcut Hulls: Vertex-restricted Outer Simplifications of Polygons
Annika Bonerath, Jan-Henrik Haunert, Joseph S. B. Mitchell +1
Let be a crossing-free polygon and a set of shortcuts, where each shortcut is a directed straight-line segment connecting two vertices of . A shortcut hull of $…
Computing Coordinated Motion Plans for Robot Swarms: The CG:SHOP Challenge 2021
Sándor P. Fekete, Phillip Keldenich, Dominik Krupke +1
We give an overview of the 2021 Computational Geometry Challenge, which targeted the problem of optimally coordinating a set of robots by computing a family of collision-free traje…
Approximating Maximum Independent Set for Rectangles in the Plane
Joseph S. B. Mitchell
We give a polynomial-time constant-factor approximation algorithm for maximum independent set for (axis-aligned) rectangles in the plane. Using a polynomial-time algorithm, the bes…