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
Project: J. ACM, Volume�26, Issue�3, Page(s) �415-421.
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
DOI: 10.1145/322139.322142
Appears in Collections:資訊科學與工程學系所

Show full item record

Google ScholarTM




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