14 citations · 64 across the 19 of their papers we have counts for
16 papers · 1 filter
Untangling Segments in the Plane
Guilherme D. da Fonseca, Yan Gerard, Bastien Rivier
A set of n segments in the plane may form a Euclidean TSP tour, a tree, or a matching, among others. Optimal TSP tours as well as minimum spanning trees and perfect matchings have…
Further Connectivity Results on Plane Spanning Path Reconfiguration
Valentino Boucard, Guilherme D. da Fonseca, Bastien Rivier
Given a finite set of points, we consider the following reconfiguration graph. The vertices are the plane spanning paths of and there is an edge between two vertices if…
Shadoks Approach to Knapsack Polygonal Packing
Guilherme D. da Fonseca, Yan Gerard
The 2024 edition of the CG:SHOP Challenge focused on the knapsack polygonal packing problem. Each instance consists of a convex polygon known as the container and a multiset of ite…
Short Flip Sequences to Untangle Segments in the Plane
Guilherme D. da Fonseca, Yan Gerard, Bastien Rivier
A (multi)set of segments in the plane may form a TSP tour, a matching, a tree, or any multigraph. If two segments cross, then we can reduce the total length with the following flip…
Optimal Area-Sensitive Bounds for Polytope Approximation
Sunil Arya, Guilherme D. da Fonseca, David M. Mount
Approximating convex bodies is a fundamental problem in geometry. Given a convex body in for a fixed dimension , the objective is to minimize the number of fa…
Economical Convex Coverings and Applications
Sunil Arya, Guilherme D. da Fonseca, David M. Mount
Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex b…
Convex Covering Using Collections of Convex Polygons and Set Cover
Guilherme D. da Fonseca
In the convex covering problem, we are given a convex polygon with holes and the goal is to cover using a small number of convex polygons that lie inside . In this paper…
On the Longest Flip Sequence to Untangle Segments in the Plane
Guilherme D. da Fonseca, Yan Gerard, Bastien Rivier
A set of segments in the plane may form a Euclidean TSP tour or a matching, among others. Optimal TSP tours as well as minimum weight perfect matchings have no crossing segments, b…
Complexity Results on Untangling Red-Blue Matchings
Arun Kumar Das, Sandip Das, Guilherme D. da Fonseca +2
Given a matching between n red points and n blue points by line segments in the plane, we consider the problem of obtaining a crossing-free matching through flip operations that re…
Greedy and Local Search Heuristics to Build Area-Optimal Polygons
Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard
In this paper, we present our heuristic solutions to the problems of finding the maximum and minimum area polygons with a given set of vertices. Our solutions are based mostly on t…
Optimal Bound on the Combinatorial Complexity of Approximating Polytopes
Rahul Arya, Sunil Arya, Guilherme D. da Fonseca +1
This paper considers the question of how to succinctly approximate a multidimensional convex body by a polytope. Given a convex body of unit diameter in Euclidean -dimension…
Approximate Convex Intersection Detection with Applications to Width and Minkowski Sums
Sunil Arya, Guilherme D. da Fonseca, David M. Mount
Approximation problems involving a single convex body in -dimensional space have received a great deal of attention in the computational geometry community. In contrast, works i…
Near-Optimal -Kernel Construction and Related Problems
Sunil Arya, Guilherme D. da Fonseca, David M. Mount
The computation of (i) -kernels, (ii) approximate diameter, and (iii) approximate bichromatic closest pair are fundamental problems in geometric approximation. In this…
Optimal Approximate Polytope Membership
Sunil Arya, Guilherme D. da Fonseca, David M. Mount
In the polytope membership problem, a convex polytope in is given, and the objective is to preprocess into a data structure so that, given a query point ,…
Approximate Polytope Membership Queries
Sunil Arya, Guilherme D. da Fonseca, David M. Mount
In the polytope membership problem, a convex polytope in is given, and the objective is to preprocess into a data structure so that, given any query point $q…
On the Combinatorial Complexity of Approximating Polytopes
Sunil Arya, Guilherme D. da Fonseca, David M. Mount
Approximating convex bodies succinctly by convex polytopes is a fundamental problem in discrete geometry. A convex body of diameter is given in Euclidean …