notesum.ai

Published at December 3

cs.CG

cs.DS

Released Date: December 3, 2024

Authors: Oliver Chubet, Don Sheehy, Siddharth Sheth

Clarkson $(P)$ :
1	Start with any point $p_{0}\in P$ and make a FVD with just one cell, $\mathsf{V}(p_{0})$ .
2	Initialize the greedy permutation $GP$ to be a list containing just $p_{0}$ .
3	Maintain a max-heap $H$ of the sites in which the key is the out-radius.
4	While the length of $GP$ is less than $\|P\|$ :
5	Let $p=\mathsf{removemax}(H)$ .
6	Let $p^{\prime}=\mathsf{farthest}(p)$ .
7	Append $p^{\prime}$ to $GP$ .
8	Insert $p^{\prime}$ into the FVD.
9	Update the keys of any cell whose radius changed.
10	Insert $p$ and $p^{\prime}$ into the heap.
11	Return $GP$ .