Geometric Algorithms Lab

The Geometric Algorithms Lab is a research group at the Ulsan National Institute of Technology (UNIST). Led by Dr. Antoine Vigneron, Associate Professor of Computer Science and Engineering, our team conducts research in computational geometry, and focuses on the design and analysis of worst-case efficient algorithms for geometric problems.

Our research areas include:

circumcircle

Geometric Optimization

Geometric optimization refers to optimization problems involving geometric objects such as points, lines or balls. These problems are motivated by applications in operations research, statistics and computer vision.

robots

Path Planning

The goal is to find feasible or optimal paths in geometric environments. This can involve obstacles, direction constraints and anistropic metrics.

patternmatching

Geometric Pattern Matching

The goal is to find occurrences of a pattern inside a set of geometric objects. These objects can be, for instance, points in Euclidean space, polygons, polyhedra or balls. We may look for a pattern under various transformations such as translations or rigid motions.

Selected Publications

  1. 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. Video.
  2. 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.
  3. 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.
  4. Geometric optimization and sums of algebraic functions. Antoine Vigneron. ACM Transactions on Algorithms 10(1):4 (2014). Preliminary version in SODA 2010. Manuscript.
  5. 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.