Zobrazeno 1 - 10
of 35
pro vyhledávání: '"Guilherme D. da Fonseca"'
Publikováno v:
Lecture Notes in Computer Science book series
WALCOM 17th International Conference and Workshops on Algorithms and Computation
WALCOM 17th International Conference and Workshops on Algorithms and Computation, Mar 2023, Hsinchu, Taiwan. pp.102-112, ⟨10.1007/978-3-031-27051-2_10⟩
WALCOM: Algorithms and Computation ISBN: 9783031270505
WALCOM 17th International Conference and Workshops on Algorithms and Computation
WALCOM 17th International Conference and Workshops on Algorithms and Computation, Mar 2023, Hsinchu, Taiwan. pp.102-112, ⟨10.1007/978-3-031-27051-2_10⟩
WALCOM: Algorithms and Computation ISBN: 9783031270505
International audience; 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 algori
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ce8a31ffd1cef34c30049145aa39ecd6
https://hal.science/hal-04051496/file/On_the_Longest_Flip_Sequence_to_Untangle_Segments_in_the_Plane_FGR22.pdf
https://hal.science/hal-04051496/file/On_the_Longest_Flip_Sequence_to_Untangle_Segments_in_the_Plane_FGR22.pdf
Autor:
Loïc Crombez, Guilherme D. Da Fonseca, Florian Fontan, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, Luc Libralesso, Benjamin Momège, Jack Spalding-Jamieson, Brandon Zhang, Da Wei Zheng
Publikováno v:
ACM Journal of Experimental Algorithmics
ACM Journal of Experimental Algorithmics, 2023, ⟨10.1145/3588869⟩
ACM Journal of Experimental Algorithmics, 2023, ⟨10.1145/3588869⟩
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:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e056bae234d00abfc1436c4afc3bff78
Publikováno v:
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) ISBN: 9781611977554
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0737d24e69637134bea6e3ac35ea8303
https://doi.org/10.1137/1.9781611977554.ch70
https://doi.org/10.1137/1.9781611977554.ch70
Autor:
Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, Luc Libralesso
Publikováno v:
ACM Journal of Experimental Algorithmics
ACM Journal of Experimental Algorithmics, 2022, 27, pp.1-17. ⟨10.1145/3524133⟩
ACM Journal of Experimental Algorithmics, 2022, 27, pp.1-17. ⟨10.1145/3524133⟩
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 their targets without collisions and minimizing the makespan. It is a cl
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::42de14dd0df8f4a4fe9b40abe8571b06
https://hal.science/hal-04051506
https://hal.science/hal-04051506
Publikováno v:
Discrete Applied Mathematics
Discrete Applied Mathematics, Elsevier, 2018, ⟨10.1016/j.dam.2018.05.049⟩
Discrete Applied Mathematics, 2018, ⟨10.1016/j.dam.2018.05.049⟩
Discrete Applied Mathematics, Elsevier, 2018, ⟨10.1016/j.dam.2018.05.049⟩
Discrete Applied Mathematics, 2018, ⟨10.1016/j.dam.2018.05.049⟩
We consider the maximum (weight) independent set problem in unit disk graphs. The high complexity of the existing polynomial-time approximation schemes motivated the development of faster constant approximation algorithms. In this paper, we present a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e77dac517a9c99cfc91a181b0b078120
https://doi.org/10.1016/j.dam.2018.05.049
https://doi.org/10.1016/j.dam.2018.05.049
Publikováno v:
Journal of Mathematical Imaging and Vision
Journal of Mathematical Imaging and Vision, 2020, ⟨10.1007/s10851-020-00957-6⟩
Journal of Mathematical Imaging and Vision, 2020, ⟨10.1007/s10851-020-00957-6⟩
A set $$S \subset \mathbb {Z}^2$$ of integer points is digital convex if $${{\,\mathrm{conv}\,}}(S) \cap \mathbb {Z}^2 = S$$ , where $${{\,\mathrm{conv}\,}}(S)$$ denotes the convex hull of S. In this paper, we consider the following two problems. The
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b94a6cd4a8fb139c76b947d09d1fa16a
https://doi.org/10.1007/s10851-020-00957-6
https://doi.org/10.1007/s10851-020-00957-6
Publikováno v:
LATIN 2022: Theoretical Informatics ISBN: 9783031206238
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::59b97600a30d6196ba60c1420b5a854f
https://doi.org/10.1007/978-3-031-20624-5_44
https://doi.org/10.1007/978-3-031-20624-5_44
Publikováno v:
ACM Journal of Experimental Algorithmics
ACM Journal of Experimental Algorithmics, In press
ACM Journal of Experimental Algorithmics, In press
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 two simple algorithmic paradigms: greedy method and local search. The g
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::76885f1269a07379626716033f924f91
http://arxiv.org/abs/2106.14728
http://arxiv.org/abs/2106.14728
Publikováno v:
SODA 2020
SODA 2020, Jan 2020, Salt Lake City, United States. pp.786-805, ⟨10.1137/1.9781611975994.48⟩
SODA
SODA 2020, Jan 2020, Salt Lake City, United States. pp.786-805, ⟨10.1137/1.9781611975994.48⟩
SODA
This paper considers the question of how to succinctly approximate a multidimensional convex body by a polytope. Given a convex body $K$ of unit diameter in Euclidean $d$-dimensional space (where $d$ is a constant) and an error parameter $\varepsilon
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::487e5878cccfb29cdf569eb0000eb625
https://hal.archives-ouvertes.fr/hal-02440482
https://hal.archives-ouvertes.fr/hal-02440482
Publikováno v:
STOC
SIAM Journal on Computing
SIAM Journal on Computing, 2018, 47 (1), pp.1-51. ⟨10.1137/16M1061096⟩
SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2018, 47 (1), pp.1-51. ⟨10.1137/16M1061096⟩
SIAM Journal on Computing
SIAM Journal on Computing, 2018, 47 (1), pp.1-51. ⟨10.1137/16M1061096⟩
SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2018, 47 (1), pp.1-51. ⟨10.1137/16M1061096⟩
In the polytope membership problem, a convex polytope $K$ in $\mathbb{R}^d$ is given, and the objective is to preprocess $K$ into a data structure so that, given any query point $q \in \mathbb{R}^d$, it is possible to determine efficiently whether $q
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f495c749d7a19914c8688279d3961c9b
https://doi.org/10.1137/16m1061096
https://doi.org/10.1137/16m1061096