14 citations · 64 across the 19 of their papers we have counts for
21 papers
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 …
On persistence properties in fractional weighted spaces
G. Fonseca, F. Linares, G. Ponce
In this work we derive a point-wise formula that will allows us to study the well-posedness of initial value problem associated to nonlinear dispersive equations in fractional weig…
Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
Guilherme D. da Fonseca, Vinícius G. Pereira de Sá, Celina M. H. de Figueiredo
Numerous approximation algorithms for problems on unit disk graphs have been proposed in the literature, exhibiting a sharp trade-off between running times and approximation ratios…
Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
Guilherme D. da Fonseca, Celina M. H. de Figueiredo, Vinícius G. P. de Sá +1
A unit disk graph is the intersection graph of n congruent disks in the plane. Dominating sets in unit disk graphs are widely studied due to their application in wireless ad-hoc ne…
The Cost of Perfection for Matchings in Graphs
Emilio Vital Brazil, Guilherme D. da Fonseca, Celina de Figueiredo +1
Perfect matchings and maximum weight matchings are two fundamental combinatorial structures. We consider the ratio between the maximum weight of a perfect matching and the maximum…
Complexity dichotomy on partial grid recognition
Vinícius G. P. de Sá, Guilherme D. da Fonseca, Raphael Machado +1
Deciding whether a graph can be embedded in a grid using only unit-length edges is NP-complete, even when restricted to binary trees. However, it is not difficult to devise a numbe…