OPTIMAL REAL-TIME ALGORITHM FOR PLANAR CONVEX HULLS

被引：71

作者：

PREPARATA, FP

机构：

[1] University of Illinois, Coordinated Science Laboratory, Urbana

来源：

COMMUNICATIONS OF THE ACM | 1979年 / 22卷 / 07期

关键词：

computational geometry; convex hull; on-line algorithms; planar set of points; real-time algorithms;

D O I：

10.1145/359131.359132

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

An algorithm is described for the construction in real-time of the convex hull of a set of n points in the plane. Using an appropriate data structure, the algorithm constructs the convex hull by successive updates, each taking time O(log n), thereby achieving a total processing time O(n log n). © 1979, ACM. All rights reserved.

引用

页码：402 / 405

页数：4