{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T09:45:22Z","timestamp":1776764722587,"version":"3.51.2"},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1994,3]]},"abstract":"<jats:p> This paper first presents an algorithm for enumerating all the integer-grid points in a given convex m-gon in O(K + m + log n) time where K is the number of such grid points and n is the dimension of the m-gon, i.e., the shorter length of the horizontal and vertical sides of an axis-parallel rectangle enclosing the m-gon. The paper next gives a simple algorithm which solves a two-variable integer programming problem with m constraints in O(m log m + log n) time where n is the dimension of a convex polygon corresponding to the feasible solution space. This improves the best known algorithm in complexity and simplicity. The paper finally presents algorithms for counting the number of grid points in a triangle or a simple polygon. <\/jats:p>","DOI":"10.1142\/s0218195994000069","type":"journal-article","created":{"date-parts":[[2004,11,18]],"date-time":"2004-11-18T21:21:13Z","timestamp":1100812873000},"page":"69-85","source":"Crossref","is-referenced-by-count":8,"title":["EFFICIENT ENUMERATION OF GRID POINTS IN A CONVEX POLYGON AND ITS APPLICATION TO INTEGER PROGRAMMING"],"prefix":"10.1142","volume":"04","author":[{"given":"NAOYOSHI","family":"KANAMARU","sequence":"first","affiliation":[{"name":"Faculty of Engineering, Tohoku University, Sendai 980, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"TAKAO","family":"NISHIZEKI","sequence":"additional","affiliation":[{"name":"Faculty of Engineering, Tohoku University, Sendai 980, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"TETSUO","family":"ASANO","sequence":"additional","affiliation":[{"name":"Osaka Electro-Communication University, Neyagawa 572, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195994000069","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:30:59Z","timestamp":1565123459000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195994000069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,3]]},"references-count":0,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1994,3]]}},"alternative-id":["10.1142\/S0218195994000069"],"URL":"https:\/\/doi.org\/10.1142\/s0218195994000069","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,3]]}}}