A Time-Optimal Delaunay Refinement Algorithm in Two Dimensions
<|reference_start|>A Time-Optimal Delaunay Refinement Algorithm in Two Dimensions: We propose a new refinement algorithm to generate size-optimal quality-guaranteed Delaunay triangulations in the plane. The algorithm takes $O(n \log n + m)$ time, where $n$ is the input size and $m$ is the output size. This is the first time-optimal Delaunay refinement algorithm.<|reference_end|>
@article{har-peled2005a,
    title={A Time-Optimal Delaunay Refinement Algorithm in Two Dimensions},
    author={Sariel Har-Peled and Alper Ungor},
    journal={arXiv preprint arXiv:cs/0501007},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0501007},
    primaryClass={cs.CG}
}