ABSTRACT
In the current chapter, we discuss approximation algorithms for partitioning a rectangle with interior points. This problem is denoted by RG-P in which RG stands for rectangle and P stands for points. An instance of the RG-P problem is a set P of n points inside a rectangle R in the plane. A feasible solution is a rectangular partition, which consists of a set of (orthogonal) line segments that partition R into rectangles such that each of the n points in P is on a partitioning line segment. The objective of the RG-P problem is to find a rectangular partition whose line segments have least total length. The RG-P problem is an NP-hard problem [1].
