×

Polygon cutting: Revisited. (English) Zbl 0971.68625

Akiyama, Jin (ed.) et al., Discrete and computational geometry. Japanese conference, JCDCG ’98. Tokyo, Japan, December 9-12, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1763, 81-92 (2000).
Summary: Given a simple polygon \(P\) on \(n\) vertices \(v_0, v_1,\dots, v_{n-1}\) with each edge assigned a non-negative weight \(w_i\), we show how to compute in \(O(n)\) time a segment \(v_ib\) (where \(b\) is a point on the boundary) that partitions \(P\) into two polygons each having weight at most \(2/3\) the weight of \(P\). If instead of edge weights, we consider an infinitely additive measure of the interior (such as the area of \(P\)), there still exists a segment \(v_ib\) that partitions \(P\) into two polygons each having measure at most \(2/3\) the measure of \(P\). In the case where \(P\) contains \(k\) points in its interior with each point assigned a non-negative weight, then in \(O(n+ k\log n)\) time a segment \(v_ib\) can be computed that partitions \(P\) into two polygons having weight at most \(2/3\) the weight of \(P\). In the case of rectilinear polygons, rectilinear cuts having the above properties exist, however, the fraction is \(3/4\) instead of \(2/3\). We present examples showing that these bounds are tight in the worst case.
We show that in \(O(n)\) time using \(O(\log n)\) cuts, a simple polygon can be partitioned into two groups \(G_1\) and \(G_2\) of pieces, such that the ratio of the area of \(G_1\) to the area of \(G_2\) is \(x:y\) for any \(x,y> 0\), \(G_1\) can be made a single piece, and all but possibly one of the cuts are diagonals of the polygon.
Finally, we present an \(O(n)\) time algorithm for finding the shortest chord in a convex polygon \(P\) that cuts off \(\alpha\) times the area of \(P\).
For the entire collection see [Zbl 0933.00046].

MSC:

68U99 Computing methodologies and applications
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite