COVERING 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:02Z	-
dc.date.available	2014-12-08T15:05:02Z	-
dc.date.issued	1992	en_US
dc.identifier.issn	0020-7160	en_US
dc.identifier.uri	http://hdl.handle.net/11536/3562	-
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 closed region bounded by a convex polygon P with n vertices such that size of this set is minimal. We use continued fraction expansions to explore the combinatorial properties of this problem and propose an O(n + log m) approximation algorithm which guarantees finite performance ratio.	en_US
dc.language.iso	en_US	en_US
dc.subject	APPROXIMATION ALGORITHM	en_US
dc.subject	CONTINUED FRACTION EXPANSIONS	en_US
dc.subject	HITTING SET PROBLEM	en_US
dc.subject	NUMBER THEORY	en_US
dc.title	COVERING GRID POINTS IN A CONVEX POLYGON WITH STRAIGHT-LINES	en_US
dc.type	Article	en_US
dc.identifier.journal	INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS	en_US
dc.citation.volume	42	en_US
dc.citation.issue	3-4	en_US
dc.citation.spage	137	en_US
dc.citation.epage	156	en_US
dc.contributor.department	資訊工程學系	zh_TW
dc.contributor.department	Department of Computer Science	en_US
dc.identifier.wosnumber	WOS:A1992JL15500002	-
dc.citation.woscount	0	-
Appears in Collections:	Articles