6 papers · 1 filter
Approximate Nearest Neighbor Searching with Non-Euclidean and Weighted Distances
Ahmed Abdelkader, Sunil Arya, Guilherme D. da Fonseca +1
We present a new approach to approximate nearest-neighbor queries in fixed dimension under a variety of non-Euclidean distances. We are given a set of points in $\mathbb{R}…
Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring
Loïc Crombez, Guilherme D. da Fonseca, Florian Fontan +8
CG:SHOP is an annual geometric optimization challenge and the 2022 edition proposed the problem of coloring a certain geometric graph defined by line segments. Surprisingly, the to…
Shadoks Approach to Low-Makespan Coordinated Motion Planning
Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard +3
This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge. This year's problem is to coordinate the motion of multiple robots in order to reach th…
Efficient Algorithms for Battleship
Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard
We consider an algorithmic problem inspired by the Battleship game. In the variant of the problem that we investigate, there is a unique ship of shape which has bee…
Efficient Algorithms to Test Digital Convexity
Loïc Crombez, Guilherme D. da Fonseca, Yan Gérard
A set is digital convex if , where denotes the convex hull of . In this paper, we consider the algorithmic prob…
Peeling Digital Potatoes
Loïc Crombez, Guilherme D. da Fonseca, Yan Gérard
The potato-peeling problem (also known as convex skull) is a fundamental computational geometry problem and the fastest algorithm to date runs in time for a polygon with $…