完整後設資料紀錄
DC 欄位語言
dc.contributor.authorLee, Hsuan-Shihen_US
dc.contributor.authorChang, Ruei Chuanen_US
dc.date.accessioned2014-12-08T15:32:50Z-
dc.date.available2014-12-08T15:32:50Z-
dc.date.issued1993-09-01en_US
dc.identifier.issn0218-1959en_US
dc.identifier.urihttp://dx.doi.org/10.1142/S0218195993000191en_US
dc.identifier.urihttp://hdl.handle.net/11536/22914-
dc.description.abstractIn 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.en_US
dc.language.isoen_USen_US
dc.subjectApproximation algorithmsen_US
dc.subjectcontinued fraction expansionsen_US
dc.subjecthitting set problemen_US
dc.subjectnumber theoryen_US
dc.titleREGULAR ENUMERATION OF GRID POINTS IN A CONVEX POLYGONen_US
dc.typeArticleen_US
dc.identifier.doi10.1142/S0218195993000191en_US
dc.identifier.journalINTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONSen_US
dc.citation.volume3en_US
dc.citation.issue3en_US
dc.citation.spage305en_US
dc.citation.epage322en_US
dc.contributor.department資訊工程學系zh_TW
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.identifier.wosnumberWOS:000208795500006-
dc.citation.woscount1-
顯示於類別:期刊論文