共 1 条
- [1] Shamos Michael Ian, 1976, 17TH P ANN IEEE S F, P208
OPTIMAL ALGORITHM FOR FINDING THE KERNEL OF A POLYGON
被引：89
作者：
LEE, DT
[1
]
PREPARATA, FP
[1
]
机构：
[1] UNIV ILLINOIS,URBANA,IL 61801
关键词：
computational complexity;
kernel of polygon;
optimal algorithms;
simple polygon;
D O I：
10.1145/322139.322142
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
The kernel K(P) of a simple polygon P wah n verUces is the locus of the points internal to P from which all verUces of P are wslble Equwalently, K(P) is the mtersectmn of appropriate half-planes determined by the polygon's edges Although it is known that to find the intersection of n generic half-planes requires time O(n log n), we show that one can exploit the ordering of the half-planes corresponding to the sequence of the polygon's edges to obtain a kernel finding algorithm which runs m time O(n) and is therefore optimal. © 1979, ACM. All rights reserved.
引用
收藏
页码：415 / 421
页数：7
相关论文