ON HITTING GRID POINTS IN A CONVEX POLYGON WITH STRAIGHT-LINES

Full metadata record

DC Field	Value	Language
dc.contributor.author	LEE, HS	en_US
dc.contributor.author	CHANG, RC	en_US
dc.date.accessioned	2014-12-08T15:05:23Z	-
dc.date.available	2014-12-08T15:05:23Z	-
dc.date.issued	1991	en_US
dc.identifier.issn	0302-9743	en_US
dc.identifier.uri	http://hdl.handle.net/11536/3924	-
dc.description.abstract	We consider the following problem: Find a set of parallel straight lines with equal spacing to hit all m grid points in a dosed region bounded by a convex polygon P with n vertices such that no grid points in a plane fall between two adjacent lines of these parallel lines and size of this set is minimal. We use continued fraction expansions to explore the combinatorial properties of this problem and propose an O(n + logm) approximation algorithm which guarantees finite performance ratio.	en_US
dc.language.iso	en_US	en_US
dc.title	ON HITTING GRID POINTS IN A CONVEX POLYGON WITH STRAIGHT-LINES	en_US
dc.type	Article; Proceedings Paper	en_US
dc.identifier.journal	LECTURE NOTES IN COMPUTER SCIENCE	en_US
dc.citation.volume	557	en_US
dc.citation.spage	176	en_US
dc.citation.epage	189	en_US
dc.contributor.department	資訊科學與工程研究所	zh_TW
dc.contributor.department	Institute of Computer Science and Engineering	en_US
dc.identifier.wosnumber	WOS:A1991LE79800018	-
Appears in Collections:	Conferences Paper