Publications

Google Scholar, DBLP

In refereed international journals

  1. Embeddings and near-neighbor searching with constant additive error for hyperbolic spaces. Eunku Park and Antoine Vigneron. Computational Geometry: Theory and Applications 126: 102150 (2025). Manuscript in arXiv:2402.14604.
  2. Maximum Coverage by k Lines. Chaeyoon Chung, Antoine Vigneron and Hee-Kap Ahn. Symmetry 16(2): 206 (2024).
  3. Coordinated Path Planning through Local Search and Simulated Annealing. Hyeyun Yang and Antoine Vigneron. ACM Journal of Experimental Algorithmics 27:3.3 1-14 (2022). Video.
  4. Matching sets of line segments. Hyeyun Yang and Antoine Vigneron. Theoretical Computer Science 866: 82-95 (2021).
  5. Approximating a planar convex set using a sparse grid. Aditya Bhaskara and Antoine Vigneron. Information Processing Letters 149: 10-13 (2019).
  6. Tight bounds for beacon-based coverage in simple rectilinear polygons. Sang Won Bae, Chan-Su Shin and Antoine Vigneron. Computational Geometry: Theory and Applications 80: 40-52 (2019). Manuscript in arXiv:1505.05106.
  7. Faster algorithms for growing prioritized disks and rectangles. Hee-Kap Ahn, Sang Won Bae, Jongmin Choi, Matias Korman, Wolfgang Mulzer, Eunjin Oh, Ji-won Park, André van Renssen and Antoine Vigneron. Computational Geometry: Theory and Applications 80: 23-39 (2019). Manuscript in arXiv:1704.07580.
  8. Finding Largest Common Point Sets. Juyoung Yon, Siu-Wing Cheng, Otfried Cheong and Antoine Vigneron. International Journal of Computational Geometry and Applications 27(3): 177-185 (2017). Manuscript.
  9. Navigating weighted regions with scattered skinny tetrahedra. Siu-Wing Cheng, Man-Kwun Chiu, Jiongxin Jin and Antoine Vigneron. International Journal of Computational Geometry and Applications 27(1&2): 13-32 (2017). Special issue for ISAAC 2015. Manuscript.
  10. A faster algorithm for computing straight skeletons. Siu-Wing Cheng, Liam Mencel and Antoine Vigneron. ACM Transactions on Algorithms 12(3): 44 (2016). Manuscript in arXiv:1405.4691.
  11. Computing the Gromov hyperbolicity of a discrete metric space. Hervé Fournier, Anas Ismail and Antoine Vigneron. Information Processing Letters 115(6-8): 576-579 (2015). Preliminary version in arXiv:1210.3323.
  12. A faster algorithm for computing motorcycle graphs. Antoine Vigneron and Lie Yan. Discrete & Computational Geometry 52(3): 492-514 (2014). Special issue on SoCG 2013. Manuscript in arXiv:1303.5958.
  13. A generalization of the convex Kakeya problem. Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, Joachim Gudmundsson, Takeshi Tokuyama and Antoine Vigneron. Algorithmica 70(2): 152-170 (2014). Special issue for LATIN 2012. Preliminary version in arXiv:1209.2171.
  14. Geometric optimization and sums of algebraic functions. Antoine Vigneron. ACM Transactions on Algorithms 10(1):4 (2014). Manuscript.
  15. Generating realistic roofs over a rectilinear polygon. Hee-Kap Ahn, Sang Won Bae, Christian Knauer, Mira Lee, Chan-Su Shin and Antoine Vigneron. Computational Geometry: Theory and Applications 46(9): 1042-1055 (2013).
  16. A deterministic algorithm for fitting a step function to a weighted point-set. Hervé Fournier and Antoine Vigneron. Information Processing Letters 113(3): 51-54 (2013). Preliminary version in arXiv:1109.1152.
  17. Covering and piercing disks with two centers. Hee-Kap Ahn, Sang-Sub Kim, Christian Knauer, Lena Schlipf, Chan-Su Shin and Antoine Vigneron. Computational Geometry: Theory and Applications 46(3): 253-262 (2013). Preliminary version in arXiv:1201.1198.
  18. Approximate shortest homotopic paths in weighted regions. Siu-Wing Cheng, Jiongxin Jin, Antoine Vigneron and Yajun Wang. International Journal of Computational Geometry and Applications 22(1): 83-102 (2012). Special issue for ISAAC 2010. Manuscript.
  19. Computing the discrete Fréchet distance with imprecise input. Hee-Kap Ahn, Marc Scherfenberg, Christian Knauer, Lena Schlipf, and Antoine Vigneron. International Journal of Computational Geometry and Applications, 22(1): 27-44 (2012). Special issue for ISAAC 2010. Manuscript.
  20. Reachability by paths of bounded curvature in a convex polygon. Hee-Kap Ahn, Otfried Cheong, Jirí Matoušek, and Antoine Vigneron. Computational Geometry: Theory and Applications 45(1-2): 21-32 (2012). Preliminary version in arXiv:1008.4244.
  21. The aligned k-center problem. Peter Brass, Christian Knauer, Hyeon-Suk Na, Chan-Su Shin, and Antoine Vigneron. International Journal of Computational Geometry and Applications 21(2): 157-178 (2011). Preliminary version in arXiv:0902.3282.
  22. Reverse nearest neighbor queries in fixed dimension. Otfried Cheong, Antoine Vigneron, and Juyoung Yon. International Journal of Computational Geometry and Applications 21(2): 179-188 (2011). Preliminary version in arXiv:0905.4441.
  23. Fitting a step function to a point set. Hervé Fournier and Antoine Vigneron. Algorithmica 60(1): 95-109 (2011). On invitation, special issue on ESA 2008. Manuscript, slides.
  24. Querying approximate shortest paths in anisotropic regions. Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang. SIAM Journal on Computing 39(5): 1888-1918 (2010). Manuscript, slides.
  25. Approximate shortest paths in anisotropic regions. Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang. SIAM Journal on Computing 38(3): 802-824 (2008). Manuscript, french slides.
  26. Sparse geometric graphs with small dilation. Boris Aronov, Mark de Berg, Otfried Cheong, Joachim Gudmundsson, Herman Haverkort, Michiel Smid, and Antoine Vigneron. Computational Geometry: Theory and Applications 40(3): 207-219 (2008). Manuscript in arXiv:cs/0702080.
  27. A tight lower bound for computing the diameter of a 3D convex polytope. Hervé Fournier and Antoine Vigneron. Algorithmica 49(3): 245-257 (2007). Manuscript, slides.
  28. Maximizing the overlap of two planar convex sets under rigid motions. Hee-Kap Ahn, Otfried Cheong, Chong-Dae Park, Chan-Su Shin, and Antoine Vigneron. Computational Geometry: Theory and Applications 37(1): 3-15 (2007). On invitation, special issue on SoCG 2005. Manuscript.
  29. Motorcycle graphs and straight skeletons. Siu-Wing Cheng and Antoine Vigneron. Algorithmica 47(2): 159-182 (2007). Manuscript.
  30. Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets. Hee-Kap Ahn, Peter Brass, Otfried Cheong, Hyeon-Suk Na, Chan-Su Shin, and Antoine Vigneron. Computational Geometry: Theory and Applications 33(3): 152-164 (2006). Manuscript, french slides.
  31. The Voronoi diagram of curved objects. Helmut Alt, Otfried Cheong, and Antoine Vigneron. Discrete & Computational Geometry 34(3): 439-453 (2005). Manuscript.
  32. Packing two disks into a polygonal environment. Prosenjit Bose, Pat Morin, and Antoine Vigneron. Journal of Discrete Algorithms 2(3): 373-380 (2004). Manuscript.
  33. Reporting intersections among thick objects. Antoine Vigneron. Information Processing Letters 85(2): 87-92 (2003). Manuscript.
  34. Computing farthest neighbors on a convex polytope. Otfried Cheong, Chan-Su Shin, and Antoine Vigneron. Theoretical Computer Science 296(1): 47-58 (2003). On invitation, special issue on COCOON 2001. Manuscript.
  35. Polynomial time algorithms for three-label point labeling.. Rob Duncan, Jianbo Qian, Antoine Vigneron, and Binhai Zhu. Theoretical Computer Science 296(1): 75-87 (2003). On invitation, special issue on COCOON 2001. Manuscript.
  36. An elementary algorithm for reporting intersections of red/blue curve segments. Jean-Daniel Boissonnat and Antoine Vigneron. Computational Geometry: Theory and Applications 21(3): 167-175 (2002). Manuscript.
  37. An algorithm for finding a k-median in a directed tree. Antoine Vigneron, Lixin Gao, Mordecai J. Golin, Giuseppe F. Italiano, and Bo Li. Information Processing Letters 74(1-2): 81-88 (2000). Manuscript.

In refereed international conference proceedings

  1. Pattern matching in doubling spaces. Corentin Allair and Antoine Vigneron. In Proc. 17th Algorithms and Data Structures Symposium (WADS 2021), LNCS 12808: 57-70. Manuscript in arXiv:1704.07580.
  2. A simulated annealing approach to coordinated motion planning. Hyeyun Yang and Antoine Vigneron. In Proc. 37th International Symposium on Computational Geometry (SoCG 2021), 65:1-65:9.
  3. Matching sets of line segments. Hyeyun Yang and Antoine Vigneron. In Proc. 13th International Conference and Workshop on Algorithms and Computation (WALCOM 2019), LNCS 11355: 261-273.
  4. Faster algorithms for growing prioritized disks and rectangles. Hee-Kap Ahn, Sang Won Bae, Jongmin Choi, Matias Korman, Wolfgang Mulzer, Eunjin Oh, Ji-Won Park, André van Renssen and Antoine Vigneron. In Proc. 28th International Symposium on Algorithms and Computation (ISAAC 2017), LNCS 9472: 3:1-3:13. Manuscript in arXiv:1704.07580.
  5. Reachability in a planar subdivision with direction constraints. Daniel Binham, Pedro Machado Manhães de Castro and Antoine Vigneron. In Proc. 33rd International Symposium on Computational Geometry (SoCG 2017), pages 17:1-17:15.
  6. Tight bounds for beacon-based coverage in simple rectilinear polygons. Sang Won Bae, Chan-Su Shin and Antoine Vigneron. In Proc. 12th Latin American Symposium on Theoretical Informatics (LATIN 2016), LNCS 9644: 110-122. Manuscript in arXiv:1505.05106.
  7. Navigating weighted regions with scattered skinny tetrahedra. Siu-Wing Cheng, Man-Kwun Chiu, Jiongxin Jin and Antoine Vigneron. In Proc. 26th International Symposium on Algorithms and Computation (ISAAC 2015), LNCS 9472: 35-45.
  8. Triangulation refinement and approximate shortest paths in weighted regions. Siu-Wing Cheng, Jiongxin Jin and Antoine Vigneron. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pages 1626-1640.
  9. A faster algorithm for computing straight skeletons. Siu-Wing Cheng, Liam Mencel and Antoine Vigneron. In Proc. 16th European symposium on Algorithms (ESA 2014), LNCS 8937: 272-283.
  10. A faster algorithm for computing motorcycle graphs. Antoine Vigneron and Lie Yan. In Proc. 29th Symposium on Computational Geometry (SoCG 2013), pages 17-26.
  11. A generalization of the convex Kakeya problem. Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, Joachim Gudmundsson, Takeshi Tokuyama and Antoine Vigneron. In Proc. 10th Latin American Symposium on Theoretical Informatics (LATIN 2012), LNCS 7256: 1-12.
  12. Covering and piercing disks with two centers. Hee-Kap Ahn, Sang-Sub Kim, Christian Knauer, Lena Schlipf, Chan-Su Shin and Antoine Vigneron. In Proc. 22st International Symposium on Algorithms and Computation (ISAAC 2011), LNCS 7074: 50-59.
  13. Generating realistic roofs over a rectilinear polygon. Hee-Kap Ahn, Sang Won Bae, Christian Knauer, Mira Lee, Chan-Su Shin and Antoine Vigneron. In Proc. 22st International Symposium on Algorithms and Computation (ISAAC 2011), LNCS 7074: 60-69.
  14. Approximate shortest homotopic paths in weighted regions. Siu-Wing Cheng, Jiongxin Jin, Antoine Vigneron and Yajun Wang. In Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010), LNCS 6507: 109-120.
  15. Computing the discrete Fréchet distance with imprecise input. Hee-Kap Ahn, Marc Scherfenberg, Christian Knauer, Lena Schlipf, and Antoine Vigneron. In Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010), LNCS 6507: 422-433.
  16. Geometric optimization and sums of algebraic functions. Antoine Vigneron. In Proc. 21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pages 906-917.
  17. Fitting a step function to a point set. Hervé Fournier and Antoine Vigneron. In Proc. 16th Annual European Symposium on Algorithms (ESA 2008), LNCS 5193: 442-453.
  18. Space-time tradeoffs for proximity searching in doubling spaces. Sunil Arya, David Mount, Antoine Vigneron, and Jian Xia. In Proc. 16th Annual European Symposium on Algorithms (ESA 2008), LNCS 5193: 112-123. Manuscript.
  19. Querying approximate shortest paths in anisotropic regions. Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang. In Proc. 23rd ACM Symposium on Computational Geometry (SoCG 2007), pages 84-91.
  20. Approximate shortest paths in anisotropic regions. Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang. In Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pages 766-774.
  21. Lower bounds for geometric diameter problems. Hervé Fournier and Antoine Vigneron. In Proc. 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), LNCS 3887: 467-478.
  22. Sparse geometric graphs with small dilation. Boris Aronov, Mark de Berg, Otfried Cheong, Joachim Gudmundsson, Herman Haverkort, and Antoine Vigneron. In Proc. 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005), LNCS 3827: 50-59.
  23. Maximizing the overlap of two planar convex sets under rigid motions. Hee-Kap Ahn, Otfried Cheong, Chong-Dae Park, Chan-Su Shin, and Antoine Vigneron. In Proc. 21st ACM Symposium on Computational Geometry (SoCG 2005), pages 356-363.
  24. Approximation algorithms for inscribing or circumscribing an axially symmetric polygon to a convex polygon. Hee-Kap Ahn, Peter Brass, Otfried Cheong, Hyeon-Suk Na, Chan-Su Shin, and Antoine Vigneron. In Proc. 10th Annual International Computing and Combinatorics Conference (COCOON 2004), LNCS 3106: 259-268.
  25. Motorcycle graphs and straight skeletons. Siu-Wing Cheng and Antoine Vigneron. In Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), pages 156-165.
  26. Packing two disks into a polygonal environment. Prosenjit Bose, Pat Morin and Antoine Vigneron. In Proc. 7th Annual International Computing and Combinatorics Conference (COCOON 2001), LNCS 2108: 142-149.
  27. Computing farthest neighbors on a convex polytope. Otfried Cheong, Chan-Su Shin and Antoine Vigneron. In Proc. 7th Annual International Computing and Combinatorics Conference (COCOON 2001), LNCS 2108: 191-200.
  28. Reachability by paths of bounded curvature in convex polygons. Hee-kap Ahn, Otfried Cheong, Jirí Matoušek and Antoine Vigneron. In Proc. 16th ACM Symposium on Computational Geometry (SoCG 2000), pages 251-259.

Others

  1. A new Trajectory similarity measure for GPS data. Anas Ismail and Antoine Vigneron. In Proc. 6th ACM SIGSPATIAL International Workshop on GeoStreaming (IWGS 2015). Manuscript.
  2. Protein structure prediction with a half coarse grained model and empirical functions. Tristan Bitard-Feildel, Antoine Vigneron and Jean-François Gibrat. Journées Ouvertes en Biologie, Informatique et Mathématiques (JOBIM 2011), pages 283-284.