A fast las vegas algorithm for triangulating a simple polygon |
| |
| Authors: | Kenneth L Clarkson Robert E Tarjan Christopher J Van Wyk |
| |
| Institution: | (1) AT&T Bell Laboratories, 07974 Murray Hill, NJ, USA;(2) Department of Computer Science, Princeton University, 08544 Princeton, NJ, USA |
| |
| Abstract: | We present a randomized algorithm that triangulates a simple polygon onn vertices inO(n log*n) expected time. The averaging in the analysis of running time is over the possible choices made by the algorithm; the bound holds for any input polygon.Research partially supported by the National Science Foundation under Grant No. DCR-8605962. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
