Optimal output-sensitive convex hull algorithms in two and three dimensions |
| |
| Authors: | T M Chan |
| |
| Institution: | (1) Department of Computer Science, University of British Columbia, V6T 1Z4 Vancouver, British Columbia, Canada |
| |
| Abstract: | We present simple output-sensitive algorithms that construct the convex hull of a set ofn points in two or three dimensions in worst-case optimalO (n logh) time andO (n) space, whereh denotes the number of vertices of the convex hull.
This research was supported by a Killam Predoctoral Fellowship and an NSERC Postgraduate Scholarship. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
