標題: | REGULAR ENUMERATION OF GRID POINTS IN A CONVEX POLYGON |
作者: | Lee, Hsuan-Shih Chang, Ruei Chuan 資訊工程學系 Department of Computer Science |
關鍵字: | Approximation algorithms;continued fraction expansions;hitting set problem;number theory |
公開日期: | 1-九月-1993 |
摘要: | In this paper we present an efficient algorithm for enumerating all the grid points in a convex polygon, where the enumeration is done by scanning the grid points with a set of parallel grid lines. Given a convex n-gon, enumeration can be done in O(K + + log min{root l/omega, l}) time, where K is the number of the grid points reported, l is the diameter of the polygon and omega is the length of the shorter sides of the rectangle enclosing the polygon with longer sides parallel to the line segment connecting the diametral pair of the polygon. We also show that the ratio of the number of the scanned grid lines to the minimal is less than some constant. |
URI: | http://dx.doi.org/10.1142/S0218195993000191 http://hdl.handle.net/11536/22914 |
ISSN: | 0218-1959 |
DOI: | 10.1142/S0218195993000191 |
期刊: | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS |
Volume: | 3 |
Issue: | 3 |
起始頁: | 305 |
結束頁: | 322 |
顯示於類別: | 期刊論文 |