Zobrazeno 1 - 10
of 95
pro vyhledávání: '"Da Fonseca, Guilherme D."'
Given a finite set $ S $ of points, we consider the following reconfiguration graph. The vertices are the plane spanning paths of $ S $ and there is an edge between two vertices if the two corresponding paths differ by two edges (one removed, one add
Externí odkaz:
http://arxiv.org/abs/2407.00244
Autor:
da Fonseca, Guilherme D., Gerard, Yan
We describe the heuristics used by the Shadoks team in the CG:SHOP 2024 Challenge. Each instance consists of a convex polygon called container and a multiset of items, where each item is a simple polygon and has an associated value. The goal is to pa
Externí odkaz:
http://arxiv.org/abs/2403.20123
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 operation. We remove a pair of crossing segments, and insert a pair o
Externí odkaz:
http://arxiv.org/abs/2307.00853
Approximating convex bodies is a fundamental question in geometry and has a wide variety of applications. Given a convex body $K$ of diameter $\Delta$ in $\mathbb{R}^d$ for fixed $d$, the objective is to minimize the number of vertices (alternatively
Externí odkaz:
http://arxiv.org/abs/2306.15648
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 $S$ of $n$ points in $\mathbb{R}^d$, an approximation parameter $\varepsilon > 0$, and a distance func
Externí odkaz:
http://arxiv.org/abs/2306.15621
Autor:
Crombez, Loïc, da Fonseca, Guilherme D., Fontan, Florian, Gerard, Yan, Gonzalez-Lorenzo, Aldo, Lafourcade, Pascal, Libralesso, Luc, Momège, Benjamin, Spalding-Jamieson, Jack, Zhang, Brandon, Zheng, Da Wei
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 top three teams used the same technique, called conflict optimization. T
Externí odkaz:
http://arxiv.org/abs/2303.09632
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 body $K$ and $\epsilon> 0$, a covering is a collection of convex bodies
Externí odkaz:
http://arxiv.org/abs/2303.08349
Autor:
da Fonseca, Guilherme D.
Publikováno v:
In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 67:1-67:9, 2023
We describe the heuristics used by the Shadoks team in the CG:SHOP 2023 Challenge. The Challenge consists of 206 instances, each being a polygon with holes. The goal is to cover each instance polygon with a small number of convex polygons. Our genera
Externí odkaz:
http://arxiv.org/abs/2303.07696
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, but several heuristics and approximation algorithms may produce solutio
Externí odkaz:
http://arxiv.org/abs/2210.12036
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 replace two crossing segments by two non-crossing ones. We first show th
Externí odkaz:
http://arxiv.org/abs/2202.11857