标题: APPROXIMATING VERTICES OF A CONVEX POLYGON WITH GRID POINTS IN THE POLYGON
作者: LEE, HS
CHANG, RC
资讯工程学系
Department of Computer Science
公开日期: 1992
摘要: In this paper, we consider the problem of approximating a vertex of a convex polygon by an integer point in the polygon. We show that the nearest grid point in a convex polygon to a vertex can be found if it exists, or decided to be nonexistent, in time O(n + logl), where l is the diameter of the polygon and a is the number of the polygon's vertices. The underlying technique used in the continued fraction expansion.
URI: http://hdl.handle.net/11536/3557
ISSN: 0302-9743
期刊: LECTURE NOTES IN COMPUTER SCIENCE
Volume: 650
起始页: 269
结束页: 278
显示于类别:Articles