Please use this identifier to cite or link to this item:
標題: An Optimal Algorithm for Finding the Kernel of a polygon
作者: D.T.Lee
關鍵字: computatmnal complexay, optimal algorithms, simple polygon, kernel of polygon CR CATEGORIES 4 49, 5 25, 5 32
出版社: ACM New York, NY, USA
摘要: 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
ISSN: 0004-5411
Appears in Collections:資訊科學與工程學系所



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.