Browse Prior Art Database

Improved Bounds for Rectangular and Guillotine Partitions

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

Publishing Venue

Software Patent Institute

Related People

Teofilo Conza.lcz: AUTHOR [+4]

Abstract

We study the problem of partitioning a rectangle R with a set of interior points Q into rectangles by introducing a set of line segments of least total length. The set of partitioning line segments must, include every point in Q. Since this problem is computationally intractable ( NF'-hard ), several approximation algorithms for its solution have been developed. In tltis paper we show that'the length of an optimal guillotine partition is not greater than 1.75 the length of an optimal rectangular part.it,ion. Since an optimal guillotine partition can 1>c obtained quickly, we. have an efficient approximation a.lgorithrn for finding near-optimal rectangular partitions. Keywords: approximation algorithms, partition of rectilinear polygons, polynomial time complexity, guillol,ine partitions, computational geometry. i flii* rm:,aro!i w: m ~y>fu>rtucl in part hr the \atimnal Scienct, 1'<;m1(1:11 ion under (;I-:I o DC li - H:,tlalfia 2

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

Page 1 of 15

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Improved Bounds for Rectangular and Guillotine Partitions

Teofilo Conza.lcz Si-Qing Zheng

IW Erart,ment of Cornlmler Science

,July 1986

Improved Bounds for Rectangular and Guillotine Partitionst

Teofilo Gonzalez and Si-ding 7heng Department of Computer Science University of California Santa. Barbara, CA 93106

Abstract:

We study the problem of partitioning a rectangle R with a set of interior points Q into rectangles by introducing a set of line segments of least total length. The set of partitioning line segments must, include every point in Q. Since this problem is computationally intractable ( NF'-hard ), several approximation algorithms for its solution have been developed. In tltis paper we show that'the length of an optimal guillotine partition is not greater than 1.75 the length of an optimal rectangular part.it,ion. Since an optimal guillotine partition can 1>c obtained quickly, we. have an efficient approximation a.lgorithrn for finding near-optimal rectangular partitions.

Keywords: approximation algorithms, partition of rectilinear polygons, polynomial time complexity, guillol,ine partitions, computational geometry. i flii* rm:,aro!i w: m ~y>fu>rtucl in part hr the \atimnal Scienct, 1'<;m1(1:11 ion under (;I-:I o DC li - H:,tlalfia

Introduction.

Given a, rectangular boundary S and a set Q of points inside S, we study the problem of partitioning S into rectangles in such a way that every point in Q lies on at. least one of the partitioning line segments and the total length of the partitioning line segments is least possible. Such a partition is called an optimal rectangular partition. Linga.s et. al. (I,PRS) show that finding an optimal rectangular partition is a, computationally intractable problem ( NP-hard ). Since then several approximation algorithms have been proposed, i.e., algorithms for which

(Equation Omitted)

is the set of partitioning line segments given by the approximation algorithm, Eor,,(I) is the set of partitioning line segments in an optimal solution, c is some constant, and 1,t:N(F,(I)) is the sum of the length of the partitioning line segments in E(I). Gonzalez and 7heng (G71] present a divide-and-conquer approximation algorithm that generates solutions such that

(Equation Omitted)

University of California at Santa Barbara Page 1 Dec 31, 1986

Page 2 of 15

Improved Bounds for Rectangular and Guillotine Partitions

The time complexity for their algorithm is O( n'' ), where n is the number of points in set. Q. Recently, Levcopoulos (1.,2) showed that it is possible to implement this approximation algorithm in O( n log n ) time. In [Gf2J an ( nr ) approximation algorithm that guarantees solutions such that

(Equation Omitted)

The approximation bound is smaller than the one in [(;7,1), however there is a substantial difference between the time complexity of these two algorithms. The algorithm in (G7,2] consists of two steps. In the first, step,...