4 Search Results for "Vigneron, Antoine"

Document
DOI: 10.4230/LIPIcs.ESA.2023.28
On k-Means for Segments and Polylines

Authors: Sergio Cabello and Panos Giannopoulos

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We study the problem of k-means clustering in the space of straight-line segments in ℝ² under the Hausdorff distance. For this problem, we give a (1+ε)-approximation algorithm that, for an input of n segments, for any fixed k, and with constant success probability, runs in time O(n + ε^{-O(k)} + ε^{-O(k)} ⋅ log^O(k) (ε^{-1})). The algorithm has two main ingredients. Firstly, we express the k-means objective in our metric space as a sum of algebraic functions and use the optimization technique of Vigneron [Antoine Vigneron, 2014] to approximate its minimum. Secondly, we reduce the input size by computing a small size coreset using the sensitivity-based sampling framework by Feldman and Langberg [Dan Feldman and Michael Langberg, 2011; Feldman et al., 2020]. Our results can be extended to polylines of constant complexity with a running time of O(n + ε^{-O(k)}).
Cite as

Sergio Cabello and Panos Giannopoulos. On k-Means for Segments and Polylines. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 28:1-28:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cabello_et_al:LIPIcs.ESA.2023.28,
  author =	{Cabello, Sergio and Giannopoulos, Panos},
  title =	{{On k-Means for Segments and Polylines}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{28:1--28:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.28},
  URN =		{urn:nbn:de:0030-drops-186812},
  doi =		{10.4230/LIPIcs.ESA.2023.28},
  annote =	{Keywords: k-means clustering, segments, polylines, Hausdorff distance, Fr\'{e}chet mean}
}
Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2021.65
A Simulated Annealing Approach to Coordinated Motion Planning (CG Challenge)

Authors: Hyeyun Yang and Antoine Vigneron

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

Abstract
The third computational geometry challenge was on a coordinated motion planning problem in which a collection of square robots need to move on the integer grid, from their given starting points to their target points, and without collision between robots, or between robots and a set of input obstacles. We designed and implemented an algorithm for this problem, which consists of three parts. First, we computed a feasible solution by placing middle-points outside of the minimum bounding box of the input positions of the robots and the obstacles, and moving each robot from its starting point to its target point through a middle-point. Second, we applied a simple local search approach where we repeatedly delete and insert again a random robot through an optimal path. It improves the quality of the solution, as the robots no longer need to go through the middle-points. Finally, we used simulated annealing to further improve this feasible solution. We used two different types of moves: We either tightened the whole trajectory of a robot, or we stretched it between two points by making the robot move through a third intermediate point generated at random.
Cite as

Hyeyun Yang and Antoine Vigneron. A Simulated Annealing Approach to Coordinated Motion Planning (CG Challenge). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 65:1-65:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{yang_et_al:LIPIcs.SoCG.2021.65,
  author =	{Yang, Hyeyun and Vigneron, Antoine},
  title =	{{A Simulated Annealing Approach to Coordinated Motion Planning}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{65:1--65: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.65},
  URN =		{urn:nbn:de:0030-drops-138649},
  doi =		{10.4230/LIPIcs.SoCG.2021.65},
  annote =	{Keywords: Path planning, simulated annealing, local search}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.3
Faster Algorithms for Growing Prioritized Disks and Rectangles

Authors: Hee-Kap Ahn, Sang Won Bae, Jongmin Choi, Matias Korman, Wolfgang Mulzer, Eunjin Oh, Ji-won Park, André van Renssen, and Antoine Vigneron

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
Motivated by map labeling, we study the problem in which we are given a collection of n disks in the plane that grow at possibly different speeds. Whenever two disks meet, the one with the higher index disappears. This problem was introduced by Funke, Krumpe, and Storandt[IWOCA 2016]. We provide the first general subquadratic algorithm for computing the times and the order of disappearance. Our algorithm also works for other shapes (such as rectangles) and in any fixed dimension. Using quadtrees, we provide an alternative algorithm that runs in near linear time, although this second algorithm has a logarithmic dependence on either the ratio of the fastest speed to the slowest speed of disks or the spread of the disk centers (the ratio of the maximum to the minimum distance between them). Our result improves the running times of previous algorithms by Funke, Krumpe, and Storandt [IWOCA 2016], Bahrdt et al. [ALENEX 2017], and Funke and Storandt [EWCG 2017]. Finally, we give an \Omega(n\log n) lower bound on the problem, showing that our quadtree algorithms are almost tight.
Cite as

Hee-Kap Ahn, Sang Won Bae, Jongmin Choi, Matias Korman, Wolfgang Mulzer, Eunjin Oh, Ji-won Park, André van Renssen, and Antoine Vigneron. Faster Algorithms for Growing Prioritized Disks and Rectangles. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 3:1-3:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.ISAAC.2017.3,
  author =	{Ahn, Hee-Kap and Bae, Sang Won and Choi, Jongmin and Korman, Matias and Mulzer, Wolfgang and Oh, Eunjin and Park, Ji-won and van Renssen, Andr\'{e} and Vigneron, Antoine},
  title =	{{Faster Algorithms for Growing Prioritized Disks and Rectangles}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{3:1--3:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.3},
  URN =		{urn:nbn:de:0030-drops-82199},
  doi =		{10.4230/LIPIcs.ISAAC.2017.3},
  annote =	{Keywords: map labeling, growing disks, elimination order}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.17
Reachability in a Planar Subdivision with Direction Constraints

Authors: Daniel Binham, Pedro Machado Manhaes de Castro, and Antoine Vigneron

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

Abstract
Given a planar subdivision with n vertices, each face having a cone of possible directions of travel, our goal is to decide which vertices of the subdivision can be reached from a given starting point s. We give an O(n log n)-time algorithm for this problem, as well as an Omega(n log n) lower bound in the algebraic computation tree model. We prove that the generalization where two cones of directions per face are allowed is NP-hard.
Cite as

Daniel Binham, Pedro Machado Manhaes de Castro, and Antoine Vigneron. Reachability in a Planar Subdivision with Direction Constraints. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{binham_et_al:LIPIcs.SoCG.2017.17,
  author =	{Binham, Daniel and Manhaes de Castro, Pedro Machado and Vigneron, Antoine},
  title =	{{Reachability in a Planar Subdivision with Direction Constraints}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{17:1--17: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.17},
  URN =		{urn:nbn:de:0030-drops-72022},
  doi =		{10.4230/LIPIcs.SoCG.2017.17},
  annote =	{Keywords: Design and analysis of geometric algorithms, Path planning, Reachability}
}
  • Refine by Author
  • 3 Vigneron, Antoine
  • 1 Ahn, Hee-Kap
  • 1 Bae, Sang Won
  • 1 Binham, Daniel
  • 1 Cabello, Sergio
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 1 Computing methodologies → Motion path planning

  • Refine by Keyword
  • 2 Path planning
  • 1 Design and analysis of geometric algorithms
  • 1 Fréchet mean
  • 1 Hausdorff distance
  • 1 Reachability
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2017
  • 1 2021
  • 1 2023

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 Imprint Privacy Contact