FINDING A MAXIMUM SET OF INDEPENDENT CHORDS IN A CIRCLE

標題:	FINDING A MAXIMUM SET OF INDEPENDENT CHORDS IN A CIRCLE
作者:	CHANG, RC LEE, HS 資訊工程學系 Department of Computer Science
關鍵字:	CIRCLE GRAPH;COMBINATORIAL PROBLEMS;COMPUTATIONAL GEOMETRY;MAXIMUM INDEPENDENT SET;POLYGON DECOMPOSITION
公開日期:	14-Feb-1992
摘要:	In this note we propose an O(nm) algorithm for finding a maximum independent set of m chords which are incident to , vertices on a circle. This result can be applied to improving the time complexity of the algorithm for partitioning simple polygons into a minimum number of uniformly monotone polygons.
URI:	http://dx.doi.org/10.1016/0020-0190(92)90262-T http://hdl.handle.net/11536/3521
ISSN:	0020-0190
DOI:	10.1016/0020-0190(92)90262-T
期刊:	INFORMATION PROCESSING LETTERS
Volume:	41
Issue:	2
起始頁:	99
結束頁:	102
Appears in Collections:	Articles

Files in This Item:

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.