# S-hull: a fast radial sweep-hull routine for Delaunay triangulation

arXiv: https://arxiv.org/abs/1604.01428 · HTML: https://mlsanity.com/paper/1604.01428/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Mar 2016.

## Built on by (most cited first, 1 of 1)

- [Learning Geometric Combinatorial Optimization Problems using Self-attention and Domain Knowledge](https://mlsanity.com/paper/2107.01759/) (2021)

## Abstract (arXiv)

A new O(nlog(n)) algorithm is presented for performing Delaunay triangulation of sets of 2D points. The novel component of the algorithm is a radially propagating sweep-hull (sequentially created from the radially sorted set of 2D points, giving a non-overlapping triangulation), paired with a final triangle flipping step to give the Delaunay triangluation. In empirical tests the algorithm runs in approximately half the time of q-hull for 2D Delaunay triangulation on randomly generated point sets.