Font Size: a A A

Cutting a polygon with a line

Posted on:2009-01-20Degree:M.C.SType:Thesis
University:Carleton University (Canada)Candidate:Ruci, ErvinFull Text:PDF
GTID:2448390005455653Subject:Computer Science
Abstract/Summary:
Given a simple polygon P and an integer K > 1, we want to compute the set of straight lines in the Cartesian plane that cut this polygon into exactly K simple polygons. We call this set of lines a K-separator and call this problem the K-separator problem.; We present an algorithm that finds the K-separators of an n-vertex simple polygon, for all K > 0, in O(n2) total time.; We prove that the decision problem given an integer K > 2 and an edge of the polygon, is there a line through this edge that cuts the polygon in exactly K pieces?, is 3SUM-HARD. For the special case when K = 2, we show that the decision problem can be solved in O(n log(n)) time.
Keywords/Search Tags:Polygon, Problem
Related items