Search Results

Documents authored by da Fonseca, Guilherme D.

Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2024.84
Shadoks Approach to Knapsack Polygonal Packing (CG Challenge)

Authors: Guilherme D. da Fonseca and Yan Gerard

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
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 pack some of the items inside the container using translations, in order to maximize the sum of their values. Our strategy consists of obtaining good initial solutions and improving them with local search. To obtain the initial solutions we used integer programming and a carefully designed greedy approach.
Cite as

Guilherme D. da Fonseca and Yan Gerard. Shadoks Approach to Knapsack Polygonal Packing (CG Challenge). In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 84:1-84:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dafonseca_et_al:LIPIcs.SoCG.2024.84,
  author =	{da Fonseca, Guilherme D. and Gerard, Yan},
  title =	{{Shadoks Approach to Knapsack Polygonal Packing}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{84:1--84:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.84},
  URN =		{urn:nbn:de:0030-drops-200293},
  doi =		{10.4230/LIPIcs.SoCG.2024.84},
  annote =	{Keywords: Packing, polygons, heuristics, integer programming, computational geometry}
}
Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2023.67
Shadoks Approach to Convex Covering (CG Challenge)

Authors: Guilherme D. da Fonseca

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
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 general strategy is the following. We find a big collection of large (often maximal) convex polygons inside the instance polygon and then solve several set cover problems to find a small subset of the collection that covers the whole polygon.
Cite as

Guilherme D. da Fonseca. Shadoks Approach to Convex Covering (CG Challenge). In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 67:1-67:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dafonseca:LIPIcs.SoCG.2023.67,
  author =	{da Fonseca, Guilherme D.},
  title =	{{Shadoks Approach to Convex Covering}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{67:1--67:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.67},
  URN =		{urn:nbn:de:0030-drops-179178},
  doi =		{10.4230/LIPIcs.SoCG.2023.67},
  annote =	{Keywords: Set cover, covering, polygons, convexity, heuristics, enumeration, simulated annealing, integer programming, computational geometry}
}
Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2022.71
Shadoks Approach to Minimum Partition into Plane Subgraphs (CG Challenge)

Authors: Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, and Aldo Gonzalez-Lorenzo

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
We explain the heuristics used by the Shadoks team to win first place in the CG:SHOP 2022 challenge that considers the minimum partition into plane subgraphs. The goal is to partition a set of segments into as few subsets as possible such that segments in the same subset do not cross each other. The challenge has given 225 instances containing between 2500 and 75000 segments. For every instance, our solution was the best among all 32 participating teams.
Cite as

Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, and Aldo Gonzalez-Lorenzo. Shadoks Approach to Minimum Partition into Plane Subgraphs (CG Challenge). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 71:1-71:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{crombez_et_al:LIPIcs.SoCG.2022.71,
  author =	{Crombez, Lo\"{i}c and da Fonseca, Guilherme D. and Gerard, Yan and Gonzalez-Lorenzo, Aldo},
  title =	{{Shadoks Approach to Minimum Partition into Plane Subgraphs}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{71:1--71:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.71},
  URN =		{urn:nbn:de:0030-drops-160794},
  doi =		{10.4230/LIPIcs.SoCG.2022.71},
  annote =	{Keywords: Plane graphs, graph coloring, intersection graph, conflict optimizer, line segments, computational geometry}
}
Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2021.63
Shadoks Approach to Low-Makespan Coordinated Motion Planning (CG Challenge)

Authors: Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge on motion planning. Using the heuristics outlined in this paper, our team won first place with the best solution to 202 out of 203 instances and optimal solutions to at least 105 of them.
Cite as

Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso. Shadoks Approach to Low-Makespan Coordinated Motion Planning (CG Challenge). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 63:1-63:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{crombez_et_al:LIPIcs.SoCG.2021.63,
  author =	{Crombez, Lo\"{i}c and da Fonseca, Guilherme D. and Gerard, Yan and Gonzalez-Lorenzo, Aldo and Lafourcade, Pascal and Libralesso, Luc},
  title =	{{Shadoks Approach to Low-Makespan Coordinated Motion Planning}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{63:1--63:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.63},
  URN =		{urn:nbn:de:0030-drops-138622},
  doi =		{10.4230/LIPIcs.SoCG.2021.63},
  annote =	{Keywords: heuristics, motion planning, digital geometry, shortest path}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.11
Efficient Algorithms for Battleship

Authors: Loïc Crombez, Guilherme D. da Fonseca, and Yan Gerard

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
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 S ⊂ ℤ² which has been translated in the lattice ℤ². We assume that a player has already hit the ship with a first shot and the goal is to sink the ship using as few shots as possible, that is, by minimizing the number of missed shots. While the player knows the shape S, which position of S has been hit is not known. Given a shape S of n lattice points, the minimum number of misses that can be achieved in the worst case by any algorithm is called the Battleship complexity of the shape S and denoted c(S). We prove three bounds on c(S), each considering a different class of shapes. First, we have c(S) ≤ n-1 for arbitrary shapes and the bound is tight for parallelogram-free shapes. Second, we provide an algorithm that shows that c(S) = O(log n) if S is an HV-convex polyomino. Third, we provide an algorithm that shows that c(S) = O(log log n) if S is a digital convex set. This last result is obtained through a novel discrete version of the Blaschke-Lebesgue inequality relating the area and the width of any convex body.
Cite as

Loïc Crombez, Guilherme D. da Fonseca, and Yan Gerard. Efficient Algorithms for Battleship. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{crombez_et_al:LIPIcs.FUN.2021.11,
  author =	{Crombez, Lo\"{i}c and da Fonseca, Guilherme D. and Gerard, Yan},
  title =	{{Efficient Algorithms for Battleship}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.11},
  URN =		{urn:nbn:de:0030-drops-127728},
  doi =		{10.4230/LIPIcs.FUN.2021.11},
  annote =	{Keywords: Polyomino, digital geometry, decision tree, lattice, HV-convexity, convexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.3
Approximate Convex Intersection Detection with Applications to Width and Minkowski Sums

Authors: Sunil Arya, Guilherme D. da Fonseca, and David M. Mount

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
Approximation problems involving a single convex body in R^d have received a great deal of attention in the computational geometry community. In contrast, works involving multiple convex bodies are generally limited to dimensions d <= 3 and/or do not consider approximation. In this paper, we consider approximations to two natural problems involving multiple convex bodies: detecting whether two polytopes intersect and computing their Minkowski sum. Given an approximation parameter epsilon > 0, we show how to independently preprocess two polytopes A,B subset R^d into data structures of size O(1/epsilon^{(d-1)/2}) such that we can answer in polylogarithmic time whether A and B intersect approximately. More generally, we can answer this for the images of A and B under affine transformations. Next, we show how to epsilon-approximate the Minkowski sum of two given polytopes defined as the intersection of n halfspaces in O(n log(1/epsilon) + 1/epsilon^{(d-1)/2 + alpha}) time, for any constant alpha > 0. Finally, we present a surprising impact of these results to a well studied problem that considers a single convex body. We show how to epsilon-approximate the width of a set of n points in O(n log(1/epsilon) + 1/epsilon^{(d-1)/2 + alpha}) time, for any constant alpha > 0, a major improvement over the previous bound of roughly O(n + 1/epsilon^{d-1}) time.
Cite as

Sunil Arya, Guilherme D. da Fonseca, and David M. Mount. Approximate Convex Intersection Detection with Applications to Width and Minkowski Sums. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{arya_et_al:LIPIcs.ESA.2018.3,
  author =	{Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
  title =	{{Approximate Convex Intersection Detection with Applications to Width and Minkowski Sums}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.3},
  URN =		{urn:nbn:de:0030-drops-94664},
  doi =		{10.4230/LIPIcs.ESA.2018.3},
  annote =	{Keywords: Minkowski sum, convex intersection, width, approximation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.10
Near-Optimal epsilon-Kernel Construction and Related Problems

Authors: Sunil Arya, Guilherme D. da Fonseca, and David M. Mount

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
The computation of (i) eps-kernels, (ii) approximate diameter, and (iii) approximate bichromatic closest pair are fundamental problems in geometric approximation. In each case the input is a set of points in d-dimensional space for a constant d and an approximation parameter eps > 0. In this paper, we describe new algorithms for these problems, achieving significant improvements to the exponent of the eps-dependency in their running times, from roughly d to d/2 for the first two problems and from roughly d/3 to d/4 for problem (iii). These results are all based on an efficient decomposition of a convex body using a hierarchy of Macbeath regions, and contrast to previous solutions that decomposed the space using quadtrees and grids. By further application of these techniques, we also show that it is possible to obtain near-optimal preprocessing time for the most efficient data structures for (iv) approximate nearest neighbor searching, (v) directional width queries, and (vi) polytope membership queries.
Cite as

Sunil Arya, Guilherme D. da Fonseca, and David M. Mount. Near-Optimal epsilon-Kernel Construction and Related Problems. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{arya_et_al:LIPIcs.SoCG.2017.10,
  author =	{Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
  title =	{{Near-Optimal epsilon-Kernel Construction and Related Problems}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.10},
  URN =		{urn:nbn:de:0030-drops-72257},
  doi =		{10.4230/LIPIcs.SoCG.2017.10},
  annote =	{Keywords: Approximation, diameter, kernel, coreset, nearest neighbor, polytope membership, bichromatic closest pair, Macbeath regions}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.11
On the Combinatorial Complexity of Approximating Polytopes

Authors: Sunil Arya, Guilherme D. da Fonseca, and David M. Mount

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Approximating convex bodies succinctly by convex polytopes is a fundamental problem in discrete geometry. A convex body K of diameter $diam(K)$ is given in Euclidean d-dimensional space, where $d$ is a constant. Given an error parameter eps > 0, the objective is to determine a polytope of minimum combinatorial complexity whose Hausdorff distance from K is at most eps diam(K). By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. A well-known result by Dudley implies that O(1/eps^{(d-1)/2}) facets suffice, and a dual result by Bronshteyn and Ivanov similarly bounds the number of vertices, but neither result bounds the total combinatorial complexity. We show that there exists an approximating polytope whose total combinatorial complexity is O-tilde(1/eps^{(d-1)/2}), where O-tilde conceals a polylogarithmic factor in 1/eps. This is an improvement upon the best known bound, which is roughly O(1/eps^{d-2}). Our result is based on a novel combination of both new and old ideas. First, we employ Macbeath regions, a classical structure from the theory of convexity. The construction of our approximating polytope employs a new stratified placement of these regions. Second, in order to analyze the combinatorial complexity of the approximating polytope, we present a tight analysis of a width-based variant of Barany and Larman's economical cap covering, which may be of independent interest. Finally, we use a deterministic variation of the witness-collector technique (developed recently by Devillers et al.) in the context of our stratified construction.
Cite as

Sunil Arya, Guilherme D. da Fonseca, and David M. Mount. On the Combinatorial Complexity of Approximating Polytopes. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{arya_et_al:LIPIcs.SoCG.2016.11,
  author =	{Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
  title =	{{On the Combinatorial Complexity of Approximating Polytopes}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.11},
  URN =		{urn:nbn:de:0030-drops-59034},
  doi =		{10.4230/LIPIcs.SoCG.2016.11},
  annote =	{Keywords: Polytope approximation, Convex polytopes, Macbeath regions}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact