標題: 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
顯示於類別:期刊論文