Geometric Algorithms Lab

The Geometric Algorithms Lab is a research group at 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:


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.


Path Planning

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


Straight Skeleton

The straight skeleton of a polygon is a straight-line graph obtained as the trace of the vertices when the polygon is shrunk, each edge moving at the same speed. This structure has many applications, such as the efficient computation of offset polygons and can give the edges of a roof from a building groundplan. .

Selected publications

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