research
∙
07/03/2023
Short Flip Sequences to Untangle Segments in the Plane
A (multi)set of segments in the plane may form a TSP tour, a matching, a...
share
research
∙
06/27/2023
Optimal Area-Sensitive Bounds for Polytope Approximation
Approximating convex bodies is a fundamental question in geometry and ha...
research
∙
06/27/2023
Approximate Nearest Neighbor Searching with Non-Euclidean and Weighted Distances
We present a new approach to approximate nearest-neighbor queries in fix...
research
∙
03/16/2023
Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring
CG:SHOP is an annual geometric optimization challenge and the 2022 editi...
research
∙
03/15/2023
Economical Convex Coverings and Applications
Coverings of convex bodies have emerged as a central component in the de...
research
∙
03/14/2023
Shadoks Approach to Convex Covering
We describe the heuristics used by the Shadoks team in the CG:SHOP 2023 ...
research
∙
10/21/2022
On the Longest Flip Sequence to Untangle Segments in the Plane
A set of segments in the plane may form a Euclidean TSP tour or a matchi...
research
∙
02/24/2022
Complexity Results on Untangling Red-Blue Matchings
Given a matching between n red points and n blue points by line segments...
research
∙
06/28/2021
Greedy and Local Search Heuristics to Build Area-Optimal Polygons
In this paper, we present our heuristic solutions to the problems of fin...
research
∙
03/25/2021
Shadoks Approach to Low-Makespan Coordinated Motion Planning
This paper describes the heuristics used by the Shadoks team for the CG:...
research
∙
04/15/2020
Efficient Algorithms for Battleship
We consider an algorithmic problem inspired by the Battleship game. In t...
research
∙
10/30/2019
Optimal Bound on the Combinatorial Complexity of Approximating Polytopes
Convex bodies play a fundamental role in geometric computation, and appr...
research
∙
01/15/2019
Efficient Algorithms to Test Digital Convexity
A set S ⊂Z^d is digital convex if conv(S) ∩Z^d = S, where conv(S) denote...
research
∙
12/13/2018
Peeling Digital Potatoes
The potato-peeling problem (also known as convex skull) is a fundamental...
research
∙
07/02/2018
