Browse Prior Art Database

Bounds for Rectangular and Guillotine Partitions

IP.com Disclosure Number: IPCOM000128365D
Original Publication Date: 1986-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 4 page(s) / 21K

Publishing Venue

Software Patent Institute

Related People

Teofflo Gonzalez: AUTHOR [+5]

Abstract

Given a set, of points Q inside a rectangle R, we study the problem of partitioning R, into rectangles by introducing a set of line segments of least total length. In a valid partition each point in Q must be included by at least one partitioning line segment. Since this problem is computationally intracta.bic ( NP-hard ), it is worthwhile to study approximation algorithms for its solution. In this paper we show that the length of an optimal guillotine partition is not greater than twine the length of an optimal rectangular partition. Since an optimal guillotine partition can be obtained in O( n'' ) time, where n is the number of points in Q, we have a polynomial time approximation algorithm for finding rectangular partitions.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 32% of the total text.

Page 1 of 4

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Bounds for Rectangular and Guillotine Partitions

Teofflo Gonzalez Man-Tak Shing Si-Qing Zheng

Department, of Compnter Science

.July 1986

Bounds for Rectangular and Guillotine 1'artitions$

Teofilo Gonzalez, Man-Tak Shing and Si-Cling .7.hcng Department of Computer Science University of California Santa Barbara, CA 93106

Abstract:

Given a set, of points Q inside a rectangle R, we study the problem of partitioning R, into rectangles by introducing a set of line segments of least total length. In a valid partition each point in Q must be included by at least one partitioning line segment. Since this problem is computationally intracta.bic ( NP-hard ), it is worthwhile to study approximation algorithms for its solution. In this paper we show that the length of an optimal guillotine partition is not greater than twine the length of an optimal rectangular partition. Since an optimal guillotine partition can be obtained in O( n'' ) time, where n is the number of points in Q, we have a polynomial time approximation algorithm for finding rectangular partitions.

Keywords: Approximation algorithms, partition of rectilinear polygons, polynomial time complexity, guillotine partitions, computational geometry. $T lii- ro.c*;crp, wa...nppcn-[ e

/1 rectilinear boundary is a simple polygon with the additional constraint that all of its sides are either parallel or perpendicular to each other. A hole is a simple rectilinear polygon located inside the rectilinear boundary. There cannot he holes inside a hole. 11 single point inside the boundary is called a degenerate hole. A figure is a rectilinear boundary which may contain an arbitrary number of nonoverla.pping holes. A rectangular partition of a figure is a set of line segments lying within its boundary and not, crossing any non-dogcnerate hole so that when added to the figure, the area not enclosed by holes is partitioned into rectangles that do not contain as interior points degenerate holes. The partitioning line segments are called edges. For every problem instance I and every set, of edges L( I in a, feasible solution, we use the function LI,"N( E( 1 ) ) to represent the sum of the length of the edges in E'( t ). /1 minimum edge length partition of a figure is a rectangular partition with least 1,I;N( . ) among all rectangular partitions. This problem has applications in

l,ing:ts et. al. [Ll'I?.S; developed an O(nt) algorithm to find a minirnurn edge length rectangular partition for the curse when tile boundary contains no interior holes. They also showed t.lrat when there arc interior holes, the prot> lcrn of finding rninirunm edge length reel-angnla.r partitions is NP-hard. Several approximation algorithms for the general problem exist. (see (f,1,
[I)(,"), [I,!] .wet [1,21). The algorithms with Clio smallest, approximation hound are the ones given in [1,11 and ~1,2]. Ili it, was shown that even when all the holes arc det; rolrlc...