Packing Boundary-Anchored Rectangles and Squares
Therese Biedl Ahmad Biniaz Anil Maheshwari Saeed Mehrabi


Geodesic analysis in Kendall's shape space
with epidemiological applications[This is a preprint version of an article to appear in the Journal of Mathematical Imaging and Vision  Springer with the DOI https://doi.org/10.1007/s10851-020-00945-w10.1007/s10851-020-00945-w and differs from the final published version in layout and  typographical detail.]
    
	Esfandiar Nava-YazdaniZIB
	Hans-Christian HegeZIB
	T. J. SullivanZIB,FUB
	Christoph von TycowiczZIB

    December 30, 2023
================================================================================================================================================================================================================================================================================================================================================================




Consider a set P of n points on the boundary of an axis-aligned square Q. We study the boundary-anchored packing problem on P in which the goal is to find a set of interior-disjoint axis-aligned rectangles in Q such that each rectangle is anchored (has a corner at some point in P), each point in P is used to anchor at most one rectangle, and the total area of the rectangles is maximized. Here, a rectangle is anchored at a point p in P if one of its corners coincides with p. In this paper, we show how to solve this problem in time linear in n, provided that the points of P are given in sorted order along the boundary of Q. We also consider the problem for anchoring squares and give an O(n^4)-time algorithm when the points in P lie on two opposite sides of Q.







§ INTRODUCTION


Let Q be an axis-aligned square in the plane, and let P be a set of points in Q. Call a rectangle r anchored at a point p∈ P if p is a corner of r. The anchored rectangle packing (ARP) problem is to find a set S of interior-disjoint axis-aligned rectangles in Q such that each rectangle in S is anchored at some point in P, each point in P is a corner of at most one rectangle in S, and the total area of the rectangles in S is maximized; see Figure <ref>(a). It is not known whether this problem is NP-hard. The best known approximation algorithm for this problem achieves ratio 7/12-ε due to Balas et al. <cit.>, who also studied several variants of this problem.

In this paper, we study a variant of the anchored packing problem in which all the points of P lie on the boundary of Q. We refer to this variant as the boundary-anchored rectangle packing (BARP) problem when the anchored objects are rectangles (see Figure <ref>(b)), while when we require to anchor squares instead of rectangles, we call the problem the boundary-anchored square packing (BASP) problem. We first present an algorithm that solves the BARP problem in linear time, provided that the points of P are given in sorted order along the boundary of Q (Section <ref>). Despite the simplicity of our algorithm, its correctness proof is non-trivial (Section <ref>). Then, we consider the BASP problem and give an O(n^4) algorithm for this problem when the points in P are on two opposite sides of Q (Section <ref>).





  
Related results. The rectangle packing problem is related to strip packing and bin packing problems, which are well-known optimization problems in computational geometry. Rectangle packing problems have applications in map labeling <cit.>. Balas et al. <cit.> studied several variants of the anchored packing problem; namely, the lower-left anchored rectangle packing problem in which points of P are required to be on the lower-left corners of the rectangles in R, the anchored square packing problem in which every anchored rectangles is required to be a square, and the lower-left anchored square packing problem which is a combination the two previous problems. For the lower-left rectangle packing problem, Freedman <cit.> conjectured that there is a solution that covers 50% of the area of Q. The best known lower bound of 9.1% of the area of Q is due to Dumitrescu and Tóth <cit.>. Balas et al. <cit.> presented approximation algorithms with ratios (7/12-ε) and 5/32 for anchored rectangles and anchored square, respectively. They also presented a 1/3-approximation algorithm for the lower-left anchored square packing problem, and proved that the analysis of the approximation factor is tight. Balas and Tóth <cit.> studied the combinatorial structure of maximal anchored rectangle packings and showed that the number of such distinct packings with the maximum area can be exponential in the number n of points of P; they give an exponential upper bound of 2^n C_n, where C_n denotes the nth Catalan number.

Finally, Iturriaga and Lubiw <cit.> studied the elastic labeling in which we are given a set of points on the boundary of a rectangle and the goal is to anchor rectangles to these points such that no two of them overlap. Here, elastic means that the label can have varying width and height, but each rectangle has a pre-specified fixed area. This problem is different than BARP as for the objectives of the two problems for instance, or having no pre-specified restriction on the area of the anchored rectangles in the latter.







§ BOUNDARY-ANCHORED RECTANGLES


In this section, we give a linear-time algorithm for the BARP problem. Before describing the algorithm, we first briefly argue that BARP is solvable in polynomial time.



  
An outline. It is easy to see <cit.> that in any rectangle packing the boundaries of rectangles must lie on the grid PQ: the union of the boundary of Q and the extension of inward rays from all points until they hit the opposite boundary. For each point p∈ P, there are O(n^2) potential rectangles of PQ anchored at p, and so we have a total of O(n^3) candidate rectangles from which we must pick an independent set (with respect to their intersection graph) such that the sum of the weights (defined to be the area of each rectangle) is maximized. If all points are on the boundary, then it is easy to represent each rectangle as a string (i.e., a Jordan curve) such that all strings have a point on the infinite face and two strings intersect if and only if not both rectangles should be taken; see Figure <ref>. This class of graphs is known as the outer-string graphs for which it is known that maximum-weight independent set is solvable in O(N^3) time, where N denotes the number of segments in a geometric representation of the input graph <cit.>. As such, BARP is solvable in O(n^9) time, but this is rather slow.



In this section, we give key insights that lead to a much faster algorithm. Define a cell to be a maximal rectangle not intersected by lines of the grid PQ. Given an optimum solution S, define a hole of S to be a maximal connected region of Q that is not covered by S, see Figure <ref>(b). We show the following in Section <ref>:


An optimal solution S either covers all of Q, or it has exactly one hole which is a single cell.


It is quite easy to test whether all of Q can be covered (see Lemma <ref>). In particular, this is always feasible if two points have the same x-coordinate or the same y-coordinate. In consequence, for the following discussion we assume that no two points have the same x- or y-coordinate. If we cannot cover all of Q, then we want to minimize the size of the hole. However, there are a quadratic number of cells, and more crucially, not all cells are feasible; i.e., could be holes. The second key result is therefore the following (by Theorem <ref>): 


Given the (at most four) points defining the boundary of a cell ψ, we can test in O(1) time whether some packing covers Q-ψ.


This immediately gives an O(n^2) algorithm to find the best solution of type Q-ψ: consider the cells in order, test whether they are feasible and then find the corresponding packing that maximizes the area among those that are feasible. However, it is not necessary to test each cell individually. We can characterize exactly when a cell ψ is feasible, based solely on where the supporting lines of ψ (which are either the boundary of Q or rays emanating from some points) have their endpoints. Hence, we do not need to look at individual cells, but at the list of points on the four sides, to find the minimum area hole. In the following, we describe this in more details.

We write P_ℬ (resp., P_ℒ, P_𝒯 and P_ℛ) for the points of P on the bottom (resp., left, top and right) side. For a point p in the plane, we denote by x(p) and y(p) the x- and y-coordinates of p, respectively. The following theorem, which we will prove in Section <ref>, characterizes possible optimal solutions; Figure <ref> on page fig:can_realize illustrates these configurations.

	
	Any BARP instance has an optimal solution S with i≤ 4 rectangles. Moreover (up to rotating the instance by a multiple of 90^∘ and/or reflecting horizontally) the anchor-points p_1,…,p_i used by S satisfy one of the following:
	


-3pt
		
  * i=1, and p_1 is the leftmost point of P_𝒯∪ P_ℬ.
		
  * i=2, and one of the following holds:
		


-1pt
			
  * p_1 is the bottommost point of P_ℒ and p_2 is the leftmost point of P_𝒯∪ P_ℬ, or
			
  * p_1 and p_2 are the two points of P_𝒯∪ P_ℬ with the closest x-coordinates.
		
		
  * i=3,  p_1∈ P_ℬ and p_2∈ P_𝒯∪ P_ℬ have closest x-coordinates with
			x(p_1)<x(p_2), and p_3 is the lowest point in P_ℒ.
and one of the following holds:
		


-1pt
			
  * p_1 and p_2 are the closest pair in P_ℬ, and p_3 is the lowest point of P_ℒ∪ P_ℛ.
			
  * p_1∈ P_ℬ and p_2∈ P_𝒯 are two points that have closest x-coordinates with x(p_1)<x(p_2), and p_3 is the lowest point of P_ℒ.
		

  * i=4, p_1∈ P_ℒ and p_3∈ P_ℛ have closest y-coordinates with y(p_1)>y(p_3), 
			and p_2∈ P_𝒯 and p_4∈ P_ℬ have the closest x-coordinates with x(p_4)<x(p_2).
	





  
Algorithm. Our algorithm proceeds as follows.  For each of the four rotations, for each of the two reflections, and for each rule 1, 2(a), 2(b), 3, and 4 in Theorem <ref>, compute the corresponding point set.   Each of these up to 40 point sets defines a cell H, and a packing that covers Q-H (see also Lemma <ref>).
The algorithm returns the one that has the smallest hole H.

Having P_ℒ,P_𝒯,P_ℛ, and P_ℬ sorted along the boundary of Q, 
we can also compute sorted lists of P_ℒ∪ P_ℛ and P_𝒯∪ P_ℬ in linear time.
The closest pair within each or between two of them can be computed in linear time.

The correctness will be proved in Section <ref>. The proof does not use that Q is a square, only that it
is an axis-aligned rectangle.  We hence have:

	
	The boundary anchored rectangle packing problem for n points, given in sorted order on the boundary of a rectangle, can be solved in O(n) time.




§ CORRECTNESS OF THE ALGORITHM





We first consider the cases when the square Q can be covered entirely by a packing.

 

Assume one of the following holds.
	
		

		-1pt
		
  * there exists a point p_1∈ P on a corner of Q, or
		
  * there exist two points p_1,p_2∈ P_ℒ∪ P_ℛ that have the same y-coordinates, or
		
  * there exist two points p_1,p_2∈ P_𝒯∪ P_ℬ that have the same x-coordinates.
	
Then we can cover all of Q with anchored rectangles.


In case (i), one rectangle anchored at p_1 can cover all of Q.
In case (ii) and (iii), two rectangles anchored at p_1,p_2 can
cover all of Q.


Note that if (i) holds then the algorithm will find this solution (after a suitable rotation)
in Case (1), and if (ii) or (iii) holds then the algorithm will find this solution (after a
suitable rotation) in Case (2b).  Since this solution is clearly maximal, it will be returned.
So the algorithm works correctly if one of these conditions hold.  
Since these conditions are easily tested, 
we assume for most of the remaining section that none of (i)–(iii) holds.    
(We will see that this implies that there must be a hole.)

We need some notation. Throughout this section, let S be an optimal solution for the BARP problem. The term “rectangle” now means one of the rectangles used by S. Define S to be the graph whose vertices are the rectangle-corners that are not corners of Q, and whose edges are coincident with the rectangle-sides not on the boundary of Q; see Figure <ref>(b). 

We define a max-segment of S to be a maximal chain s of collinear edges of S. We say that s is introduced if at least one endpoint of s belongs to P and is used as anchor-point for some rectangle of S. For example, in Figure <ref>(b), s_1 is introduced but s_2 is not. Every edge e belongs to exactly one max-segment s_e; we say that e is introduced if s_e is. In Figure <ref>(b), e_1, e_2 and e_3 are introduced. We already know <cit.> that all boundaries of rectangles can be assumed to lie on the grid PQ, but we need to strengthen this and prove the following: 

	
	There exists an optimal solution S such that all max-segments of S are introduced. 



Let S be an optimal solution that, among all optimal solutions, minimizes the number of max-segments.
Assume for contradiction that there exists a max-segment s that is not introduced. 
After rotation we may assume that s is horizontal.   Let V be the vertical slab defined by the 
two vertical lines through the endpoints of s; see Figure <ref>. 

	
	
Consider moving s upward in parallel, i.e., shortening the rectangles A with their bottom sides on s and lengthening the rectangles B with their top sides on s. Observe first that these rectangles indeed can be shortened/lengthened, because none of them can be anchored at a point on s: the only points of s that are possibly in P are its ends, but neither of them anchors a rectangle since s is not introduced. If this move of s increases the coverage, then S was not optimal, a contradiction. If this decreases the coverage, then moving downward in parallel would increase the coverage, a contradiction. So the covered area must remain the same during the move. Shift s up until it hits either the boundary of Q or intersects some other horizontal max-segment of S. If s hits the boundary of Q, then s disappears and will be deleted from S. If s intersects some other horizontal max-segment s' of S (which may be inside V or only share an endpoint with the translated s) then the two max-segments merge into one. Either way we decrease the number of max-segments, which contradicts the choice of S and proves the lemma.


From now on, without further mentioning, we assume that S is an optimal solution
where all max-segments are introduced. We also assume that, among all such optimal solutions, S minimizes the number of rectangles.

	
	Every internal vertex of S has degree three or four.


Every internal vertex of S resides on the corner(s) of axis-aligned rectangle(s), and so has degree at least 2 and at most 4. Assume for contradiction that there is a vertex b of S that has degree exactly 2, and
let a and c be its neighbours. After possible rotation, we may assume that 
a lies to the left of b, and c lies above b, as depicted in Figure <ref>. Thus, b is the bottom-right corner of some rectangle r_1, and no other rectangle has b on its boundary. This implies that the region to the right of bc and below ab belongs to some hole H. So rectangle r_1 is anchored either on the left or the top side of Q; after a possible diagonal flip we assume that it is anchored on the left.
	
	 

Define a_P and c_P to be the points of P that introduced ab and cb, respectively;
we know that these must be on P_ℒ respectively P_𝒯 since b has degree 2.
By definition of “introduced” some rectangle r^c is anchored at c_P.  We claim that r^c cannot have c_P as its top-right corner. Assume for contradiction that it has. Then we can expand r^c (if needed) to cover the entire rectangle spanned by a_P and c_P; this can only increase the coverage. In particular, the expanded r^c covers all of r_1. We know that r_1≠ r^c since r_1 was anchored on the left side of Q.  This contradicts that S has the minimum number of rectangles, so r^c has c_P as its top-left corner.

If the right side r_1 of r_1 is a sub-segment of bc, then we can stretch r_1 to the right to increase the coverage of S, contradicting optimality. So r_1 must be a strict super-segment of bc, which in particular implies that c is interior and has no leftward edge.  Since c is a vertex, it must have a rightward edge; let d be the vertex of H to the right of c. Let r_2 be the rectangle whose bottom-left corner is c; this exists since edge cd is the boundary of some rectangle(s), but the area below cd belongs to hole H. Rectangle r_2 cannot be anchored on the right, otherwise we could expand r^c to cover all of r_2 and reduce the number of rectangles, a contradiction. So r_2 is anchored on the top, which implies that r_2=r^c, else they would overlap.

 The rectangle r_2 is not anchored at its bottom-right corner, because otherwise we can stretch r_1 to the right and increase the coverage of S. Also, the vertex d must be interior because otherwise we can stretch r_2 down and increase the coverage of S.  TB: I still don't believe it.  What if the top-left corner of r_2 is below the top-right corner of r_1, and there is some other rectangle (anchored vertically above e_1) that sits above r_2?  Then you cannot shift r_1 rightward.  (The answer is that then we could dispense with r_2 altogether, but this is non-trivial and needs to be argued.)


If the bottom side r_2 of r_2 is a sub-segment of cd, then we can stretch r_2 down to increase the coverage of S. So r_2 is a strict super-segment of cd, which implies that d is interior. We iterate this process three times as follows. (i) Let e be the vertex of H that is below d, and let r_3 be the rectangle whose top-left corner is d. Argue as before that r_3 is anchored at the right endpoint d_P of the max-segment through cd, therefore the left side r_3 is a strict super-segment of de and e is interior. (ii) Let f be the vertex of H that is to the left of e, and let r_4 be the rectangle whose top-right corner is e. Argue as before that r_4 is anchored at the bottom endpoint e_P of the max-segment through de, therefore the top side r_4 is a strict super-segment of ef and f is interior. (iii) Finally, let g be the vertex of H that is above f (possibly g=a). Now observe that the max-segment through fg cannot reach the boundary of Q without intersecting r_4,r_1 or r_2. Therefore, fg is not introduced—a contradiction.


We assumed that neither case (ii) nor (iii) of Observation <ref> holds, which means that any grid-line of the grid PQ has exactly one end in P. So, we can direct the edges of the grid (and with it the edges of S) from the end in P to the end not in P. See also Figure <ref>. Define a guillotine cut to be a max-segment of S for which both endpoints are on the boundary of Q.




If there is no guillotine cut, then S has a hole H. Furthermore, H is a rectangle, H is not incident to the boundary of Q, and the boundary of H is a directed cycle of S.


We claim that no vertex w of S on the boundary of Q is a sink. For if the unique edge incident to w were directed from some vertex v to w, then by Lemma <ref> and the way we directed the edges of G(S), the point p that introduced vw would be on the opposite side and hence the max-segment pw would be a guillotine cut. Likewise no interior vertex w can be a sink,  because (w)≥ 3 by the previous lemma, which implies that two incident edge of w have the same orientation (horizontal or vertical). One of them then becomes outgoing at w since we direct edges along grid-lines. So S has no sink, which implies that it has a directed cycle C.
Now let a_1a_1' be a arbitrary max-segment, and assume that it is directed
a_1→ a_1', so a_1'∉P is a vertex in the interior.
Since a_1a_1' is maximal,
(a_1')≤ 3.  By the previous lemma, (a_1')≥ 3, so
(a_1')=3.  Since max-segment a_1a_1' ends at a_1', therefore
a_1' is in the interior of a segment
a_2a_2' that is perpendicular to a_1a_1'.  Say this is directed a_2→ a_2'.
Iterate the argument with max-segment a_2, so for i=2,3,4,… let a_i→ a_i' be a 
max-segment the max-segment that has a_i-1' in its interior. 
Since the graph is finite, we must repeat vertices
at some point, so let us assume (after possible renaming or starting with a different segment)
that a_i' resides on a_1a_1'.  Then a_1'→ a_2'→…→ a_i' forms a 
directed circuit in G.  This circuit need not be simple, but we can find within it a simple
directed cycle C.
The region enclosed by C has no point on
the boundary, so no rectangle anchored on the boundary can cover parts of it without intersecting C.  
So the interior region of C is a hole H not incident to the boundary.
We know that H is a rectangle since it has no vertex of degree 2
by the previous lemma, hence in particular no reflex vertex.
Let a,b,c,d be the corners of H in clockwise order with a in the bottom-left corner.
Since H was bounded by a directed cycle, we may up to symmetry assume that its sides
are directed a→ b→ c→ d.
These directions imply that the point p_B that introduced ab lies on P_ℬ, the point p_L that
introduced bc lies on P_ℒ the point p_T that introduced cd lies on P_𝒯 and the 
point p_R that introduced da lies on P_ℛ.  Since ab is the left side and cd is
the right side of H,  we have x(p_B)<x(p_T) and similarly one argues y(p_L)>y(p_R).

Observe that using four rectangles from the
four points p_B,p_L,p_T,p_R, we can easily cover Q-H.   By optimality of S,
hence H is the only hole.


We use the previous lemma in the proof of our following stronger claim.



If S has holes, then it has a hole H that is a rectangle. Furthermore, every interior corner of H has an incoming edge that lies on H.



We prove by induction on the cardinality of S. If S is empty then H=Q and we are done. Assume that S is not empty. If there is no guillotine cut, then H is a rectangle by Lemma <ref> which is interior and whose boundary is a directed cycle; this satisfies all claims. Assume now that there is a guillotine-cut aa', say it is horizontal. Since case (ii) of Observation <ref> does not hold, not both a and a' can belong to P, say a'∉P. Segment aa' divides Q into two rectangles Q_1 and Q_2 with Q_1 above Q_2; see Figure <ref>(a). There is a rectangle r_1 that is anchored at a; up to a vertical flip we may assume that r_1 is inside Q_1. Observe that r_1 must cover all of Q_1, else we could find a solution with more coverage or fewer rectangles. Thus S':=S∖{r_1} is an anchored-rectangle packing for Q_2 with anchor-points in P∖{a}. Notice that S' must be optimal for Q_2, else we could get a better packing for Q by adding r_1 to it.  It cannot cover all of Q_2 since S had holes. Therefore, S' has a hole H and by induction hypothesis H is a rectangle; observe that H is also a rectangular hole in S. This finishes our proof of the first claim.




Now, consider a corner c of H that is interior to Q. If c is interior to Q_2, then by induction hypothesis it has an incoming edge that lies on H. Assume that c is not interior to Q_2 and thus it lies on aa' and c≠ a,a'. Consider an interior vertical edge e of H; see Figures <ref>(b) and <ref>(c). Observe that e is directed upwards because otherwise the max-segment s_e containing it would have intersect r_1. It follows that all interior vertical edges of H are directed upwards. Therefore the vertical edge of H that is incident to c is also upward and hence incoming to c as desired.




First, we consider the case where H does not lie on the boundary of Q. See Figure <ref>(a). The line-segment ab is formed by the right sides of some rectangle(s). Let r_1 be one such rectangle. If r_1 is a sub-segment of ab, then r_1 is anchored at a point of P_ℒ, and thus we can stretch r_1 to the right  TB: why?  The bottom of r_1 could be below a.
and increase the coverage of ; this contradicts the optimality of . Assume that r_1 is not a sub-segment of ab,
say the top-right corner of r_1 is above b (the other case is symmetric). Let r_2 be the rectangle with bottom-right corner b.
Notice that its bottom segment r_2 is a strict super-segment of bc, because otherwise we could stretch r_2 down and increase the coverage of . Similarly, let r_3 be the rectangle with top-right corner c for which the left side r_3 is a strict super-segment of cd. Also, let r_4 be the rectangle with top-right corner d for which the top side is a super-segment of da. The resulting configuration is depicted in Figure <ref>(a). As a consequence of Lemma <ref>, all sides of H are introduced by P. Thus, this configuration of r_1, r_2, r_3, and r_4 implies that ab is introduced by a point p_1 in P_𝒯. Similarly, bc, cd, and da are introduced by points p_2, p_3, and p_4 that belong to P_ℛ, P_ℬ, and P_ℒ respectively. As shown in Figure <ref>(a), with the four points p_1, p_2, p_3, and p_4 we can cover the rest of Q. Therefore,  does not contain a second hole. 


	

Now, we consider the case where H lies on the boundary of Q. We differentiate between the following four possible configurations of H:
	
		
  * H lies on exactly one corner of Q. Without loss of generality assume that H lies on the bottom-left corner of Q as in Figure <ref>(a). The edge cd is introduced by a point p_1 that belongs to either P_𝒯 or P_ℬ. The edge bc is introduced by a point p_2 that belongs to either P_ℒ or P_ℛ. Let r_1 be a rectangle with r_1 on bc. If its bottom-right corner r_1 is to the right of c, then as a consequence of Lemma <ref>, we have that p_1=d. In this case the rest of Q can be covered by p_1 and p_2 as shown in Figure <ref>(a). So r_1 is on or to the left of c. In this case if r_1 is not anchored at p_2, then we can stretch r_1 down and increase the coverage of . Thus, r_1 is anchored at p_2, which implies that p_2=b. In this case the rest of Q can be covered by p_1 and p_2, no matter if p_1 belongs to P_𝒯 or P_ℬ.
		
  * H lies on two corners of Q. Without loss of generality assume that H lies on the left corners of Q as in Figure <ref>(b). Let p_1 be a point of P_𝒯∪ P_ℬ that is an endpoint of cd. The rest of Q can be covered by p_1.
		
  * H does not lie on any corner of Q, but lies on exactly one side of Q. Without loss of generality assume that H lies on the bottom side of Q as in Figure <ref>(c). Let p_1, p_2, and p_3 be the points of P that introduce ab, cd, and bc, respectively. 
				If none of b and c belong to the interiors of the bottom sides of some rectangles, then there exists  a rectangle r such that r is a sub-segment of bc. In this case, by stretching r down, the coverage of  can be increased, which contradicts its optimality. 
		
		If both b and c belong to the interiors of the bottom side(s) of some rectangle(s), then as a consequence of Lemma <ref> both p_1 and p_2 belong to P_ℬ. In this case the rest of Q can be covered by p_1, p_2 and p_3 as in Figure <ref>(c). 
		
		Assume that exactly one of b and c, say b, is in the interior of the bottom side of some rectangle, say r_1; Figure <ref>(d). In this case p_1 belongs to P_ℬ. Moreover, p_3 cannot be in P_ℛ, because otherwise r_1 can be stretch down and increase the coverage of , which contradicts its optimality (notice that there is no point in P_ℒ that has the same y-coordinate as p_3). Thus, p_3 belongs to P_ℒ. In this case, we can cover the rest of Q with p_1, p_2, and p_3, no matter if p_2 belongs to P_𝒯 or P_ℬ; see Figure <ref>(d). The case, where c is in the interior of the bottom side of some rectangle, can be handled analogously; see Figure <ref>(e).
		
		
  * H does not lie on any corner of Q, but lies on two sides of Q. Without loss of generality assume that H lie on the bottom and top sides of Q as in Figure <ref>(f). Let p_1 and p_2 be the points of P that introduce ab and cd. We can easily cover the rest of Q with p_1 and p_2, no matter if p_1 or p_2 belong to P_ℒ or P_𝒯.
	  




Hence, hole H must satisfy this hole-condition on the edge directions (at least for some optimal solution S); that is, every interior corner of H has an incoming edge that lies on H. It turns out that this condition is also sufficient.




Let H be a rectangle whose sides lie on PQ. If H satisfies the hole-condition, then there exists a packing that covers Q∖ H.


Let p_1,…,p_i (for some i≤ 4) be the points of P that defined
the grid lines on which the sides of H reside.  We distinguish cases (1)–(4)
depending on how many sides of H are interior, where case (2) splits further
into cases (2a) and (2b) depending on whether the sides are adjacent or parallel.
After possible rotation, the hole is situated as shown in Figure <ref>.
Every interior corner of H has an incoming edge that is on H, which (up to
reflection) forces the location of some of p_1,…,p_i as indicated in
the figure. In all cases, one verifies that i rectangles anchored at p_1,…,p_i suffice to cover Q∖ H.






Let H be a rectangle that is incident to the boundary of Q such that every interior side of H is an edge of PQ and every interior vertex of H has an incoming edge on H. Then, there exists an anchored-rectangle packing of Q∖ H.


Nothing is to show if H=Q, so assume H⊂ Q, say the top side of H is not
on Q. Assume after a possible reflection that the top side of H is directed rightward and introduced by point p_1.


  * If the top-left corner of H is interior, then the condition force it to 
be directed upward.  Say it is introduced by point p_2.  If the bottom side of
H is on Q, then we can cover Q∖ H with rectangles anchored at p_1
and p_2 (and perhaps another rectangle anchored at p_3 if the right side of
H is not on the boundary and p_3 is the point in P that introduced it.)

Then c and d are both interior vertices of H, say the side is directed
c→ d.  Then we must have b→ c by the condition on c.
Since b is on the boundary, therefore b∈ P.    Let c_P and d_P be the points of P that introduced cd and da, respectively.  We can now cover Q∖ H using three rectangles anchored at d_P, c_P and a.  See Figure <ref>.

  * Next assume that exactly two sides of H are on the boundary of Q, and they are
consecutive on H.  Say these are ab and bc.  Then d is interior, and up to
symmetry, we have c→ d by the condition on d.  Therefore c∈ P.
Let d_P be the point of P that introduced da (possibly d_P=a).  We can
now cover Q∖ H using two rectangles anchored at c and d_P.

  * Next assume that exactly two sides of H are on the boundary of Q, and they are
on opposite sides of H.  Say these are ab and cd.  Then bc and da
connect points on the boundary but lie on grid-edges, hence on of b,c belongs
to P and one of d,a belongs to P.  We can now cover Q∖ H using
two rectangles anchored at these two points.

  * Next assume that exactly three sides of H are on the boundary of Q, 
say these are ab,bc and cd.  Then da
connect two points on the boundary but lies on grid-edges, hence 
one of d,a belongs to P.  We can now cover Q∖ H using
one rectangle anchored at this point.

Nothing is to show if all sides of H lies on the boundary of Q since then
H=Q and Q∖ H is empty.



We are now ready to prove Theorem <ref>. To this end, we first show the following:


If S has holes, then it has exactly one hole H, and H is a cell of PQ.


Lemma <ref> shows that we may assume H to be a rectangle that satisfies the hole-condition. By Lemma <ref>,  we can cover Q∖ H with anchored rectangles, which by maximality of S means that H is unique.

If H is not a cell, then it is bisected by some grid-line ℓ into two pieces H_1 and H_2. If some H'∈{H_1,H_2} satisfies the hole-condition (i.e., all interior corners have incoming edges on H'), then we can create a packing that covers Q∖ H' ⊃ Q∖ H, which contradicts the minimality of S. In fact, by inspecting the possible configurations of H in cases (1), (2a), (2b), (3), and (4), as well as possible placements of the “undecided” anchor-points and the orientation/direction of ℓ (see Figure <ref>, which shows all but one case), we observe that H' satisfies the hole-condition as we can cover Q∖ H' in each of these cases. So, there is a contradiction in all cases, and H must be one cell.




By Lemma <ref>, we have characterized solutions that have holes.  It remains to characterize solutions that do not have holes; i.e., to show that conditions (i)–(iii) of Observation <ref> are necessary.



  	If Q can be covered with anchored rectangles, then one of (i), (ii) or (iii) holds.


Let S be a packing that covers all of Q. If S has no edge, then all of Q must be covered by one rectangle, which hence must be anchored at a corner of Q and (i) holds. So assume that S has edges. By Lemma <ref>, since S has no hole there must be a guillotine-cut aa', say it is horizontal. If both a and a' are in P then (ii) holds and we are done, so assume a∈ P and a'∉ P.

Recall the rectangles Q_1, Q_2 and r_1 from the proof of Lemma <ref> and observe that S':=S∖{r_1}  covers all of Q_2 using anchor-points in P':=P∖{a}. Apply induction to S',P',Q_2. If (i) holds for them, then P' has a point on a corner of Q_2, which by a,a'∉ P' is also a corner of Q and we are done. If (ii) holds for them, then two points in P'⊂ P have the same y-coordinate and we are done. Finally (iii) cannot hold for S',P',Q_2 because the top side of Q_2 has no point of P' on it since a'∉P.


We are finally ready to prove Theorem <ref>. Let S be the optimal solution with the minimum number of rectangles. If S covers all of Q, then by Lemma <ref> one of (i)–(iii) holds. If (i) holds, then the corner in P will be chosen under rule (1). (In these and all other cases, “chosen” means “after a suitable rotation and/or reflection”.) If (ii) or (iii) holds then the two points with the coinciding coordinate will be chosen under rule (2b).

If S has holes, then by Lemma <ref>
its unique hole H is a cell such that
all interior corners of H have incoming edges on H.
Let p_1,…,p_i be the points that introduce interior sides of H.
We know that H has one of the types shown in Figure <ref>,
and p_1,…,p_i hence will be considered
under the corresponding rule.  Moreover, all point sets that fit
the type can be realized by Lemma <ref>. So H
must be the one that minimizes the area, which corresponds to the
points minimizing the x-distance resp. y-distance.  So 
one of rules 1, 2a, 2b, 3 or 4 applies to the points p_1,…,p_i 
and Theorem <ref> holds.





§ BOUNDARY-ANCHORED SQUARES


Recall that Q is an axis-aligned square in the plane and P is a set of points on the boundary of Q. In the boundary anchored square packing (BASP) problem we want to find a set of disjoint axis-aligned squares in Q that are anchored at points of P and maximize the total area. For this problem we are unable to find a grid—as we did for rectangle packing—that discretizes the problem such that the sides of every square in an optimal solution lie on that grid. It might be tempting to obtain a grid as follows. For every point p on the bottom side of Q we add the following lines to the grid (see Figure <ref>(a)): 

	
  * one vertical line through p,
	
  * one horizontal line through the top side of the largest square in Q that has p on its bottom-left corner, and one for a similar square that has p on its bottom-right corner, and
	
  * for every other point q on the bottom side of Q, we add one horizontal line through the top side of the square that has the segment pq as its bottom side.


We add similar lines for points that are on the left side, the right side, and the top side of Q. Let PQ be the resulting grid. We construct a set of points for which no optimal solution of the BASP is introduced by PQ. Figure <ref>(b) shows a set of six points with an optimal solution associated for them. A point p lies on the bottom side of Q and at distance δ from the bottom-left corner of Q, for a small δ>0. Five points u,v,w,x,y arranged on the top side of Q from left to right such that w is the mid-point of the top side of Q, |vw|=|wx|=1.5δ, and |uv|=|xy|=ϵ, for a small ϵ that is much less than δ. Any optimal solution for this setting contains the largest square in Q that has p on its bottom-left corner. Also any optimal solution contains the two squares that are anchored at u and y as depicted in Figure <ref>(b). The solution shown in Figure <ref>(b) is optimal. Any optimal solution contains two squares of side-length δ and one square of side-length δ/2 that are anchored at v,w,x. The square of side-length δ/2 is not defined by PQ, no matter on which of v,w,x it is anchored.



In the rest of this section we consider two special cases where the points of P lie only on one side of Q, or on two opposite sides of Q. Later we will see that the two opposite-side case can be reduced to some instances of the one-side case. 



 §.§ Points on one side

In this section we consider a version of the BASP problem where the points of P lie only on one side of Q. We consider a more general version where Q is rectangle and the points of P lie on a longer side of Q. To avoid confusion in our notation, we use R to represent such a Q. Let w and h denote the width and height of R, respectively. We assume that the longer side of R is parallel to the x-axis and points of P lie on the bottom side of R; see Figure <ref>. We introduce a grid  such that any optimal solution for this problem is defined by . This grid contains the following lines:

	
  * a vertical line through p,
	
  * a horizontal line through the top side of the largest square in R that has p on its bottom left-corner, and one for a similar square that has p on its bottom-right corner, 
	
  * for every other point q, that is at distance at most h from p, we add one horizontal line through the top side of the square that has the segment pq as its bottom side, and
	
  * one vertical line through the right side of the largest square in R that has p on its bottom-left corner, and one for a similar square that has p on its bottom-right corner.


Based on the construction of , we define a set 𝒮 of squares that are obtained as follows. For every point p∈ P we add to 𝒮 three types of squares (see Figure <ref>(a)):

	
  T1 the largest square in R that has p on its bottom-left corner, and the largest square in R that has p on its bottom-right corner,
	
  T2 for every other point q, that is within distance h from p, we add a square that has the segment pq as its bottom side, and
	
  T3 for every other point q to the right (resp. left) of p, which is within distance 2h from p, we add a square of side length |pq|-h that has p on its bottom-left corner (resp. bottom-right corner).

The set 𝒮 contains O(n^2) squares and all of them are introduced by . We say that a square is introduced by a grid if at least three of its sides lie on the grid.  The following lemma enables us to discretize the problem.

	
Consider an optimal solution for the variant of the BASP problem where the points lie only on the bottom side of the input rectangle. Then, all squares of the solution belong to 𝒮.
	
 

	Our proof is by contradiction. Consider an optimal solution S for this problem and assume that it contains a square s that does not belong to 𝒮. Without loss of generality we assume that s has a point p on its bottom-left corner. Since s is not of type (T1), the top side of s does not lie on the top side of R. Also, the right side of s does not lie on the right side of R. If the right side of s does not touch any other square in S, then we can enlarge s and increase the total area of S which contradicts its optimality. Let r be the square that touches the right side of s. Let q be the point that r is anchored on. Since s is not of type (T2), q is the bottom-right corner of r. Moreover, since s is not of type (T3), r is not a largest square that is anchored at q.

	So, we have two touching squares s and r and none of them are maximum squares. See Figure <ref>(b). Without loss of generality assume that s is not smaller than r. By concurrently enlarging s and shrinking r by a small amount, the gain in the area of s would be larger than the loss in the area of r. This will increase the total area of S which contradicts its optimality.




As a consequence of Lemma <ref>, to solve the BASP problem, it suffices to find a subset of non-overlapping squares in 𝒮 with maximum area. For every square s∈𝒮, we introduce a closed interval I_s with the bottom side of s. We set the weight of I_s to be the area of s. Let ℐ be the set of these intervals. Any maximum-weight independent set of intervals in ℐ corresponds to a set of non-overlapping squares in 𝒮 with maximum area. A maximum-weight independent set of m intervals, given in sorted order of their left endpoints, can be computed in O(m) time <cit.>. The set 𝒮 contains O(n^2) squares and can be computed within the same time bound. Consequently, ℐ can be computed in O(n^2) time. Having the points of P sorted from left to right, the sorted order of the intervals in ℐ can be obtained within the same time bound. Thus, the total running time of our algorithm is O(n^2).



 §.§ Points on two opposite sides

In this section we study a version of the BASP problem where the points of P lie on two opposite sides of square Q. We show how to reduce an instance of this problem into O(n^2) instances of the one-sided version. Since the one-sided version can be solved in O(n^2) time, this reduction implies an O(n^4)-time solution for the two-sided version. We refer to a square that is anchored at a top point (resp. bottom point) by a top square (resp. a bottom square).   


For any optimal solution for the BASP problem, where the input points lie only on the top and bottom sides of the input square, there exists no horizontal line ℓ that intersects both a top square and a bottom square in its interior.



Suppose for a contradiction that such line ℓ exists, say it intersects a top square s and a bottom square r.

Since ℓ crosses both s and r, the height of s plus the height of r is larger than h (the height of the boundary square). This implies that their total width is also larger than h. Since s and r are non-overlapping, there is a vertical line which separates s from r. These two facts imply that the width of the boundary square is larger than h, which is a contradiction.


By Lemma <ref>, for every optimal solution there exists a horizontal line that separates its top squares from its bottom squares; refer to such a line as a separating line. We introduce a set ℒ of O(n^2) horizontal lines and claim that for every optimal solution of the BASP problem, there exists a separating line that belongs to ℒ. Assume that Q is the unit square, and its bottom-left corner is the origin. For a point p, let p_x denotes its x-coordinate. First, we add to ℒ the horizontal line y=1/2. Then, for every point p on the bottom side of Q we add the following lines to ℒ (see Figure <ref>(a)): 

	
  * y=p_x; this line represents the top side of the largest square that has p on its bottom-right corner.
	
  * y=1-p_x; this line represents the top side of the largest square that has p on its bottom-left corner.
	
  * for every point q≠ p on the bottom side of Q, we add y=|p_x-q_x|; this line represents the top side of the square that is anchored at p and has another corner at q.
	
  * for every point q≠ p on the bottom side of Q, we add y=|p_x-q_x|/2; this line represents the the top side of the square that is anchored at p and has another corner at the mid-point of the segment pq.


Then, for every point p on the top side of Q, we add to ℒ the lines analogous to items (1)–(4).



For any optimal solution of the BASP problem, there exists a separating line that belongs to ℒ. 
 

	Consider an optimal solution S for this problem. Let s be the largest square in S and, without loss of generality, assume that s is a bottom-square and that p is the bottom-left corner of s; see Figure <ref>(b). By Lemma <ref>, there exists a separating line for S. Let ℓ be the line that touches the top side of s; observe that ℓ is separating since it intersects no top square by Lemma <ref>. If ℓ is below the line y=1/2, then due to maximality of s, y=1/2 is also a separating line for S and belongs to ℒ. Assume that ℓ is above y=1/2.



The rest of our proof is by contradiction. By a similar reasoning as in the proof of Lemma <ref>, we argue that s is the only bottom square that touches ℓ. However, there might be arbitrarily many top squares that touch ℓ. Let a denote the y-coordinate of ℓ. We continuously move ℓ up and down within the vertical range [a-ϵ,a+ϵ], for a very small amount ϵ. Then, the y-coordinate of ℓ is x, where x∈[a-ϵ,a+ϵ]. While moving ℓ in this range, we change (enlarge or shrink) some squares of S as follows and keep track of their area (see Figure <ref>(b)): 

	
		
  * We change s in such a way that its top side always lies on ℓ. Thus, the are of s would be x^2.
		
  * Observe that the right side of s does not touch the boundary square because otherwise ℓ would have been added to ℒ by item (2). There can be only one square in S that touches the right side of s. If such a square exists, then let s_1 denote that square, and assume that it is anchored at a point q; see Figure <ref>(b). The point q is on the bottom-right corner of s_1 because otherwise ℓ would have been added to ℒ by item (3). We change s_1 in such a way that its left side always touches the right side of s. Thus, the area of s_1 is (|pq|-x)^2
		
  * Let S_2 be the set of all top squares that touch ℓ. We change these squares in such a way that their bottom sides touch ℓ. The area of every such square is (1-x)^2.
		
  * We construct a set S_3 of top squares as follows. Consider every square s_2∈ S_2 and let s_2 be anchored at a point u. If there is a top square s_3 in S that touches s_2 from the side that does not contain u, then we add s_3 to S_3. Let s_3 be anchored at v as depicted in Figure <ref>(b). The point v is not on the boundary of s_2 because otherwise ℓ would have been added to ℒ by item (3). Also, the square s_3 does have the same size as s_2 because otherwise ℓ would have been added to ℒ by item (4); in fact s_3 is smaller than s_2. We change s_3 in such a way that it always touches s_2. Thus, by moving ℓ in the above range, the area of s_3 will be (|uv|-(1-x))^2.
	

Let S' be the set of the above squares; i.e., S'={s,r}∪ S_2 ∪ S_3. After performing the above adjustments, the squares in S remain non-overlapping. Also the squares in S∖ S' remain unchanged. Thus, by moving ℓ on the vertical range [a-ϵ, a+ϵ], we obtain a valid solution for the BASP problem. For a given x∈ [a-ϵ, a+ϵ], the total area of the squares in S' is


    f(x)=x^2+(|pq|-x)^2+|S_2|· (1-x)^2+∑_s_3∈ S_3area(s_3),


where |S_2| denotes the cardinality of S_2. As discussed above, the area of s_3 is of the form (c-(1-x))^2 for some constant c. This implies that f(x)=α x^2+β x+γ for some constants α>0, β, and γ. This means that f(x) is a convex function on the domain [a-ϵ, a+ϵ]. Thus, the maximum value of f(x) is attained at an endpoint of the domain, but not at a. Therefore, the original solution S, for which ℓ has y-coordinate a, cannot be an optimal solution for the BASP problem.


The set ℒ contains O(n) lines per point of P, and thus, O(n^2) lines in total.
These lines can be computed in O(n^2) time. By Lemma <ref>, for every optimal solution there exists a separating line in ℒ. Therefore, by checking every line ℓ in ℒ and taking the one that maximizes the total area of the two one-sided instances of the problem (one for each side of ℓ), we can solve the two-sided version of the problem in O(n^4) time. 



  
Remark. A restricted version of the BASP problem, where every point of P should be assigned a non-zero square, can be solved in O(n) time for the one-sided case, and in O(n^2) time for the two-sided case. In the one-sided case, we have a constant number of squares/intervals per point because we only need to check its two neighbors. By a similar reason, in the two-sided case we get a constant number of lines per point, and thus, O(n) lines in total.




§ CONCLUSION


In this paper, we considered the anchored rectangle and square packing problems in which all points are on the boundary of the square Q. By exploiting the properties of an optimal solution, we gave an optimal linear-time exact algorithm for the rectangle packing problem. Observe that our algorithm covers nearly everything for large n (contrasting with the fraction of 7/12-ε achieved in the non-boundary case <cit.>). For there are (up to rotation) at least n/2 points in R_B∪ P_𝒯, which define n/2+1 vertical slabs.  Rule (1) or (2b) will consider the narrowest of them as hole, which has area at most 1/(n/2+1) if Q has area 1. So, we cover a fraction of 1-O(1/n) of Q. We also considered the square packing problem when the points on P are on two opposite sides of Q, and gave an O(n^4)-time algorithm for this problem.

The most interesting open question is to determine the complexity of the BARP or BASP problem for when the points of P can lie in the interior of Q. Is it polynomial-time solvable? As a first step, it would be interesting to characterize which polygonal curves on Q∪PS could be boundaries of a hole in a solution. Moreover, the complexity of the BASP problem when the points of P are on all four sides of Q remains open.




    Acknowledgement.
 The authors thank Paz Carmi and Luís Fernando Schultz Xavier da Silveira for helpful discussions on the problem.



plain



