# Maximizing the Overlap of Two Planar Convex Sets under Rigid Motions

Maximizing the Overlap of Two Planar Convex Sets under Rigid Motions

Hee-Kap Ahn a , Otfried Cheong b,? , Chong-Dae Park b Chan-Su Shin c , Antoine Vigneron d

a Department b Division c School d Unit? e

of Computer Science and Engineering, Sejong University, Seoul, Korea.

of Computer Science, Korea Advanced Institute of Science and Technology, Daejeon, Korea.

of Electr. and Inform. Engineering, Hankuk University of Foreign Studies, Yongin, Korea. Math?matiques et Informatique Appliqu?es, INRA, Jouy-en-Josas, France. e e

Abstract Given two compact convex sets P and Q in the plane, we compute an image of P under a rigid motion that approximately maximizes the overlap with Q. More precisely, for any ε > 0, we compute a rigid motion such that the area of overlap is at least 1 ? ε times the maximum possible overlap. Our algorithm uses O(1/ε) extreme point and line intersection queries on P and Q, plus O((1/ε2 ) log(1/ε)) running time. If only translations are allowed, the extra running time reduces to O((1/ε) log(1/ε)). If P and Q are convex polygons with n vertices in total that are given in an array or balanced tree, the total running time is O((1/ε) log n + (1/ε2 ) log(1/ε)) for rigid motions and O((1/ε) log n + (1/ε) log(1/ε)) for translations. Key words: Approximation algorithm, sublinear algorithm, convex shape, geometric pattern matching

Work by the ?rst three authors was supported by the Brain Korea 21 Project, The School of Information Technology, KAIST, in 2005. Work by the fourth author was supported by the Hankuk University of Foreign Studies Research Fund of 2005. Work by the ?fth author was supported by the National University of Singapore under grant R–252–000–166–112. ? Corresponding author. Email addresses: heekap@gmail.com (Hee-Kap Ahn), otfried@kaist.ac.kr (Otfried Cheong), cdpark@jupiter.kaist.ac.kr (Chong-Dae Park), cssin@hufs.ac.kr (Chan-Su Shin), antoine.vigneron@jouy.inra.fr (Antoine Vigneron).

Preprint submitted to Computational Geometry

24 April 2006

1

Introduction

We consider the following problem: given two compact convex sets P and Q in the plane, ?nd a rigid motion ? such that the area of ?P ∩ Q is maximized, where ?P is the image of P under ?. The area of overlap (or, equivalently, the area of the symmetric di?erence) of two planar regions is a natural measure of their similarity that is insensitive to noise [4,6]. Most previous theoretical work on the problem has restricted ? to be a translation. De Berg et al. [6] gave an O(n log n) time algorithm to solve the problem for two convex polygons with n vertices in total, making use of the Brunn-Minkowski theorem, and gave a constant-factor approximation. If ? is restricted to be a translation along a given line, then a linear time algorithm is possible [3]. Alt et al. [4] gave a constant-factor approximation for the minimum area of the symmetric di?erence. More general objects have also been considered. Mount et al. [10] studied the function mapping a translation vector to the area of overlap of a translated simple n-vertex polygon P with another simple m-vertex polygon Q, showing that it is continuous, piecewise polynomial of degree at most two, has O((nm)2 ) pieces, and can be computed within the same time bound. No algorithm is known that computes the translation maximizing the area of overlap that does not essentially construct the whole function graph. De Berg et al. [5] consider the case where P and Q are disjoint unions of n and m unit disks, with n m. They compute a (1 ? ε)-approximation for the maximal area of overlap of P and Q under translations in time O((nm/ε2 ) log(m/ε)). In contrast, surprisingly little is known about the problem if ? can be any rigid motion. Alt et al. [2] made some initial progress on a similar problem, showing, for instance, how to construct, for a convex polygon P , the axisparallel rectangle Q minimizing the symmetric di?erence of P and Q. In the case where P and Q are disjoint unions of n and m unit disks, de Berg et al. [5] compute a (1 ? ε)-approximation for the maximal area of overlap of P and Q under rigid motions in time O((n2 m2 /ε3 ) log m). Dickerson and Scharstein [8] consider the case where P is a convex m-gon, and Q a set of n points in the plane, and show how to ?nd a rigid motion of P that contains the maximum number of points in Q. Finally, Cheong et al. [7] gave a general framework for maximizing the overlap of two shapes. This framework can be applied to convex polygons, but computes an approximation with absolute error, that is, a rigid motion ? such that the area of ?P ∩Q is at least the optimal area minus ε times the area of P . No algorithm is known that solves the problem exactly. The standard approach of decomposing the con?guration space into regions where the intersection of the two polygons is combinatorially invariant does not easily lead to such an algorithm. The di?culty is that the function expressing 2

the area of intersection for a known combinatorial type is complicated, and it is not clear whether the maximum of this function can be found exactly under a realistic model of computation. Ahn et al. [1] recently gave an algorithm to ?nd an approximation to the largest axially-symmetric convex polygon included in a given convex polygon P . This can be considered a special case of our problem, where Q is a re?ected copy of P . Their solution exploits this special relationship between Q and P , and does not generalize to our more general problem. Indeed, the hardest case in the analysis of our algorithm is when P is a rather “round” polygon, and Q is long and skinny—this cannot happen in their setting. We give an algorithm that, given any ε > 0, computes a rigid motion ? such that the area of ?P ∩ Q is at least 1 ? ε times the maximum possible area. It performs O(1/ε) extreme point and line intersection queries on the convex sets P and Q, and requires additional time O((1/ε2 ) log(1/ε)). Our algorithm is in fact surprisingly simple. Given two polygons P and Q with n vertices in total, we generate a set of O(1/ε) orientations for P , and run the O(n log n) algorithm of de Berg et al. [6] to compute the optimal translation for each orientation. The total running time of this procedure is O((n log n)/ε), and the di?culty lies entirely in the selection of appropriate orientations—uniform sampling does not work, and the set of orientations needs in fact to be chosen based on the aspect ratios of P and Q—and in proving the approximation bound. Like Ahn et al. [1], we then show that we can replace the convex input sets P and Q by polygonal inner approximations, whose complexity depends on ε only (and not on the complexity of the input sets). This simpli?cation can be done entirely using two kinds of queries on the input sets, namely intersecting queries with a line, and ?nding the point extreme in a given direction. In the problems studied by Ahn et al. [1], the well-known Dudley approximation √ with O(1/ ε) vertices could be used as this inner approximation. In this paper, we introduce two new approximations that are stronger than Dudley’s in two di?erent senses, but unfortunately both require Θ(1/ε) vertices. The same inner approximations can be used to approximately solve the problem of maximizing the overlap of planar convex sets under translations. This requires O(1/ε) extreme point and line intersection queries on the convex sets P and Q, and additional time O((1/ε) log(1/ε)). If P and Q are convex n-gons, given as an array or balanced tree containing the vertices in sorted order, then the two queries can be implemented in O(log n) time. The running time of our algorithm is then O((1/ε) log n+(1/ε2 ) log(1/ε)) for rigid motions and O((1/ε) log n+(1/ε) log(1/ε)) for translations. If the convex n-gons are given di?erently, for instance as a linked list, then an additional 3

O(n) term has to be added. The reader may wonder why we cannot simply use the “naive” approach of ?rst approximating both sets using Dudley’s approximation, and then running an exact algorithm on the approximations. This approach fails for two reasons: First, as mentioned above, no exact algorithm is known, and if one is found, it is likely to be quite complicated and impractical. Second, we have not been able to prove that an exact solution to the problem for Dudley’s approximation guarantees a (1?ε)-approximation for the original sets (the proof of Claim (1) in Section 5 breaks down if we use Dudley’s approximation). It would be nice to either prove this √ it would also improve the time bound of our algorithm (as by a factor of O(1/ ε)), or to ?nd a counter-example.

2

Preliminaries

Let C denote a compact convex set in the plane. We let |C| and d(C) denote the area and diameter of C. Let w(C) denote the width of C, that is, the minimum distance between two parallel lines enclosing C. We call a pair of points (p, q) in C an antipodal grasp of C if C lies inbetween the lines through p and q orthogonal to pq, see Figure 1. The width is always achieved by an p

q

Fig. 1. An antipodal grasp.

antipodal grasp, as the following lemma shows. Lemma 1 Let C be a compact convex set in the plane. There is an antipodal grasp (p, q) of C such that the segment pq ? C has length w(C). If C is a convex n-gon, then such an antipodal grasp can be found in O(n) time. PROOF. Let 1 and 2 be two parallel lines that achieve the width. Let s1 = 1 ∩ C and s2 = 2 ∩ C (by convexity of C, these sets are either points or segments). Assume that there is no pair of points (p, q) ∈ s1 × s2 such that pq is orthogonal to 1 and 2 . (See Figure 2.) Since s1 and s2 are convex, this implies that there is a line orthogonal to 1 and 2 such that s1 and 4

p1 s1 C

1

s2 p2

2

Fig. 2. Proof of Lemma 1.

s2 lie strictly on di?erent sides of . Let p1 (resp. p2 ) denote the intersection of with 1 (resp. 2 ). If we rotate 1 slightly around p1 towards s2 , and 2 around p2 towards s1 , we obtain two parallel lines enclosing C whose distance is less than w(C), a contradiction. It follows that an antipodal grasp (p, q) realizing the width exists. In case C is a convex n-gon, we can ?nd it in O(n) time using the rotating calipers technique of Toussaint [12]. 2

We will call a segment pq as in Lemma 1 a spine of C. A similar statement for the diameter is well-known: Lemma 2 Let C be a compact convex set in the plane. Any segment pq ? C of length d(C) de?nes an antipodal grasp (p, q). Width and diameter allow us to approximate the area of a convex set. Lemma 3 Let C be a compact convex set in the plane. Then w(C)d(C)/2 |C| w(C)d(C).

PROOF. Let R be the rectangle circumscribed to C with two sides parallel to a spine of C and such that C touches all four sides of R. The sides of R have length w(C) and d d(C), and so |C| |R| = w(C)d w(C)d(C). Let now R be the rectangle circumscribed to C with two sides parallel to a diameter of C and such that again C touches all four sides of R , see Figure 3. The sides of R have length d(C) and w w(C). C contains two triangles with a common base of length d(C), and total height w. This implies |C| d(C)w/2 w(C)d(C)/2. 2 5

d(C) R w(C) w

Fig. 3. Proof of Lemma 3.

Diameter, width, and area of a convex n-gon can all be computed in linear time [12], and this is optimal. To achieve sublinear algorithms, and to handle non-polygonal convex sets, we need to be able to process two queries on convex sets. Given a convex set C, let TC be the time to answer the following two kinds of queries: (a) given a direction vector u, ?nd the point v in C extreme in direction u, that is, maximizing the dot product v, u ; and (b) given a line , ?nd the intersection ∩ C (a line segment). Obviously, TC depends on how C is represented—for instance, TC = O(log n) if C is a convex n-gon stored in an array (in sorted order), but TC = Θ(n) if it is stored in a linked list. The following lemma allows us to compute rough estimates of diameter, width, and area of a convex set using these queries. Let dist(p, q) denote the Euclidean distance between points p and q. Lemma 4 Let C be a compact convex set in the plane. In O(TC ) time we can ?nd two rectangles r and R such that: (i) r ? C ? R, with C touching all four sides of R. √ (ii) r and R are homothetic, with a homothety ratio 3 2. √ (iii) Let d and w be the lengths√ the sides of R, with d w. Then d(C)/ 2 of √ d d(C), w(C) w 2 2w(C), and |R|/(2 2) |C| |R|.

PROOF. By doing four queries, we can ?nd the axis-parallel bounding box R of C. Let a b > 0 be its sides, and pick the vertices p, q of C touching the sides √ R of length b , see Figure 4. Then a of dist(p, q) d(C) 2a . Using four more queries, we now ?nd the smallest rectand(R) gle R containing C with two sides parallel to pq. These sides have length √ a dist(p, q) a d(C)/ 2, and the other sides have length b. Since C contains two triangles with a common base pq and total height b, we have √ = ab √ √ |R| |C| √ dist(p, q)b/2 a b/2 (d(C)/ 2)b/2 √ ab/(2 2) = |R|/(2 2). √ a dist(p, q) follows d(C)b 2dist(p, q)b 2 2|C| From d(C)/ 2 √ √ 2 2w(C)d(C), so b 2 2w(C). 6

a=d p b

R R a

Fig. 4. Proof of Lemma 4.

q b=w

Let now d := max(a, b), w := min(a, b). We have d d(C), since there are points of C on each pair of opposite sides of R, and w w(C), since C is √ contained inbetween two parallel lines at distance w. So d a d(C)/ 2, √ and w b 2 2w(C), which completes the proof of (iii). √ √ Now we show how to ?nd r. Recall that dist(p, q) d(C)/ 2 a/ 2, and C contains two triangles with a common base pq and total height b. Note that one of these has height at least b/2. If it has an obtuse interior angle around p (resp. q), then it contains a homothet r of R with homothety ratio √ at least 1/(3 2) such that r has a corner at p (resp. q). Otherwise, it contains a homothet r of R with homothety ratio at least 1/4 such that r has one side lying in pq. Since we know one point of C touching each side of R, we can ?nd r in constant time. 2

Note that √ with more e?ort, better estimates can be obtained. For instance, with O(1/ ε) queries, a (1 + ε)-approximation to diameter, width, and area can be computed [1], and a homothety ratio of 2 + ε can be obtained [11]. The following lemma gives a somewhat larger inscribed rectangle, but does not permit a sublinear construction. (Alternatively, one could show the existence √ of an inscribed rectangle with sides d(C)/(2 2) and w(C)/2 using the results by Schwarzkopf et al. [11]). Lemma 5 Let C be a convex set in the plane. There is a rectangle r with sides d(C)/2 and w(C)/4 contained in C. If C is a convex n-gon, then we can compute r in O(n) time. 7

PROOF. Let pq be a diameter of C, and let R be a rectangle circumscribed to C with two sides parallel to pq such that C touches all four sides of R. Let w be the side of R orthogonal to pq, see Figure 5. Then C contains two triangles

d(C)

w

p

q

Fig. 5. Proof of Lemma 5.

with a common base pq and total height w. One of these has height at least w/2, and contains a rectangle of length dist(p, q)/2 = d(C)/2 and height at least w/4 w(C)/4. If C is a convex n-gon, then we can compute its diameter in O(n) time [12], and it is easy to ?nd r in O(n) time. 2

This implies the following lower bound on the overlap of two convex sets under rigid motions. Lemma 6 Let C1 and C2 be convex sets in the plane. There is a rigid motion ? such that |?C1 ∩ C2 | 1 · min{d(C1 ), d(C2 )} · min{w(C1 ), w(C2 )}. 8

PROOF. By Lemma 5 there are rectangles ri ? Ci of size d(Ci )/2×w(Ci )/4, for i = 1, 2. Let ? be the rigid motion maximizing |?r1 ∩ r2 |. Then |?r1 ∩ r2 | min{d(C1 )/2, d(C2 )/2} · min{w(C1 )/4, w(C2 )/4},

and the lemma follows. 2

If two convex sets are long and skinny, the rigid motion achieving maximal overlap must align them rather well. Lemma 7 Let C1 and C2 be convex sets in the plane, let ?opt be the rigid motion maximizing |?opt C1 ∩ C2 |, and let ? be the angle between spines of 8

?opt C1 and C2 . Then sin ? 8 max{w(C1 ), w(C2 )} . min{d(C1 ), d(C2 )}

PROOF. The set Ci is contained in an in?nite strip of width w(Ci ), for i = 1, 2. When these two strips make an angle of ? > 0, their intersection is a parallelogram of area w(C1 )w(C2 )/ sin ?. By Lemma 6, this area must be at least min{w(C1 ), w(C2 )} min{d(C1 ), d(C2 )}/8. This implies the lemma. 2

We will need two more results. The ?rst one is from Ahn et al. [1], the second one is by de Berg et al. [6] and makes use of the Brunn-Minkowski theorem. Lemma 8 ([1]) Let C be a convex set, and let C be a copy of C, rotated by an angle δ around a point p in C. Then |C ∩ C | or, equivalently, |C \ C | πδ d(C)2 . 2 |C| ? πδ d(C)2 , 2

Lemma 9 ([6]) Given convex polygons P and Q in the plane with n vertices in total, one can ?nd in time O(n log n) the translation τ maximizing |τ P ∩Q|.

3

An algorithm for convex polygons

Let P and Q be convex polygons with n vertices in total, and let ε > 0. Our goal is to ?nd a rigid motion ?app such that |?app P ∩ Q| (1 ? ε)|?opt P ∩ Q|, where ?opt is the rigid motion maximizing |?P ∩ Q|. We do this by computing a set of O(1/ε) orientations for P , and the optimal translation for each orientation using Lemma 9. To show the correctness of this approach, we need to prove that starting with the optimal placement of P (that is, with ?opt P ), we can rotate P either way by a certain amount and lose only ε|?opt P ∩ Q|. We distribute the proof over the following two key lemmas. Lemma 10 Let C1 , C2 be convex sets with w(C2 ) δ w(C2 ) ε . 4π min{d(C1 ), d(C2 )} 9 w(C1 ), let ε > 0, and let

Then there are clockwise and counter-clockwise rotations ρ with angle δ such that |ρ?opt C1 ∩ C2 | (1 ? ε)|?opt C1 ∩ C2 |. PROOF. In fact, any rotation ρ of angle δ around a point in ?opt C1 ∩ C2 will do. To simplify the presentation, we assume that C1 is already in the optimal placement, that is that ?opt is the identity. If d(C1 ) d(C2 ) then it su?ces to show that |(C1 ∩ C2 ) \ (ρC1 ∩ C2 )| εw(C2 )d(C1 )/8 by Lemma 6. We observe that (C1 ∩C2 )\(ρC1 ∩C2 ) ? C1 \ρC1 . πδ πε w(C2 ) ε By Lemma 8, |C1 \ ρC1 | d(C1 )2 d(C1 )2 = 8 w(C2 )d(C1 ), as 2 8π d(C1 ) required. If d(C1 ) > d(C2 ), we ?rst observe that |ρC1 ∩C2 | = |C1 ∩ρ?1 C2 |. By Lemma 6, it su?ces to show that |(C1 ∩ C2 ) \ (C1 ∩ ρ?1 C2 )| εw(C2 )d(C2 )/8. We have (C1 ∩ C2 ) \ (C1 ∩ ρ?1 C2 ) ? C2 \ ρ?1 C2 , and by Lemma 8 |C2 \ ρ?1 C2 | πδ πε ε 2 d(C2 )2 8π w(C2 )) d(C2 )2 = 8 w(C2 )d(C2 ). 2 2 d(C Lemma 11 Let C1 , C2 be convex sets with w(C2 ) w(C1 )/4 and d(C2 ) 1 w(C1 ) d(C1 )/2, let ε > 0, and let δ ε 160 d(C1 ) . Then there are clockwise and counter-clockwise rotations ρ with angle δ such that |ρ?opt C1 ∩ C2 | (1 ? ε)|?opt C1 ∩ C2 |. PROOF. Again, let us assume that C1 is already in the optimal placement, that is that ?opt is the identity. It su?ces to show the existence of the clockwise rotation—the existence of the counter-clockwise rotation then follows by applying the lemma to mirror images of C1 and C2 . Let S be an in?nite strip of width w(C2 ) containing C2 , and choose a coordinate system such that S is horizontal. Let R be the smallest axis-parallel bounding rectangle for C1 . We can assume that the distance between the upper edges of S and R is larger than the distance between the lower edges (otherwise we rotate the coordinate system by 180? ). Since w(C2 ) w(C1 )/4, and the height of R is at least w(C1 ), this implies that the distance between 3 the upper edges is at least 8 w(C1 ). Let R be that part of R that has distance at least w(C1 )/4 from the upper edge of R, see Figure 6. The distance between the upper edges of R and S is still at least 1 w(C1 ). The horizontal width of R 8 1 1 is at most d(C1 ). This implies that a line with absolute slope less than 4 w(C1 )) d(C cannot intersect both the upper edge of R and R . It follows that a line that is 1 1 tangent to C1 from above in a point u ∈ R has absolute slope at least 4 w(C1 )) . d(C Let now ρ be the rotation by angle δ, in clockwise direction, around the intersection p of the lower edge of S with the left edge of R. Since d(C2 ) d(C1 )/2, 10

R

1 4 w(C1 )

R

3 8 w(C1 )

S p

w(C2 )

d(C1 )

Fig. 6. The strip S and the rectangle R.

it su?ces by Lemma 6 to show that |(C1 ∩C2 )\(ρC1 ∩C2 )|

εw(C2 )d(C1 )/16.

Let X := (C1 ∩ C2 ) \ (ρC1 ∩ C2 ) = (C1 \ ρC1 ) ∩ C2 , and consider a point q ∈ X. Clearly q ∈ C1 . We will show below that the horizontal distance between q and the boundary of C1 is at most εd(C1 )/32. Since C1 is convex, a horizontal line intersects it in an interval (if at all). The points of X ∩ lie in the leftmost and rightmost piece of this interval, in two subintervals of total length at most εd(C1 )/16. Since q ∈ C2 , we have q ∈ S, and so it su?ces to integrate over all horizontal lines in S to establish |X| εw(C2 )d(C1 )/16, as desired. It remains to prove the following claim: the horizontal distance between a point q ∈ X and the boundary of C1 is at most εd(C1 )/32. We observe that q ∈ X implies q ∈ ρC1 , and therefore ρ?1 q ∈ C1 . Let q := ρ?1 q. The claim is true if q lies within horizontal distance εd(C1 )/32 from the left edge of R, so let us assume that is not the case. This implies that the angle that the line pq makes with a vertical line is at least arctan εd(C1 ) 32w(C2 ) εw(C1 ) 4 32 w(C1 ) ε ε arctan δ, 8 160 arctan

thus q lies above and to the left of q (that is, has smaller x-coordinate but larger y-coordinate). Since q ∈ C1 , but q ∈ C1 , the segment qq must intersect the boundary of C1 . The segment has length qq at most δd(S ∩R) δ(d(C1 )+ 1 5 w(C2 )) 4 δd(C1 ) 128 εw(C1 ). If it intersects the lower boundary of C1 , we are done: the boundary must pass above q but below q, and therefore it must intersect the horizontal line through q to the left of q, at a distance smaller than the distance between q and q , which is less than εd(C1 )/32. 11

This leaves the case where qq intersects the upper boundary of C1 . Let u be the point of intersection, and let be a tangent to C1 in u. Since the length of qq is less than 1 w(C1 ) and q ∈ S, we have u ∈ R . As we observed before, this 8 1 implies that has absolute slope at least 1 w(C1 )) . This implies that intersects 4 d(C the horizontal line through q in a point u at distance at most εd(C1 )/32 from q, see Figure 7. Since C1 lies below the line , the boundary of C1 must intersect the horizontal line through q between q and u , implying the claim, and therefore the lemma. 2

q u u εd(C1 )/32 S p

Fig. 7. dist(u , q) εd(C1 )/32.

q

We can now describe the algorithm in detail. We start by computing the diameter, width, and a spine of both polygons, in total time O(n). Without loss of generality, let w(Q) w(P ). If w(Q) w(P )/4 and d(Q) d(P )/2, then using Lemma 5 we compute in O(n) time a rectangle rP ? P with edge lengths w(Q) and d(Q). By Lemma 1 we can also ?nd in O(n) time a rectangle RQ that is circumscribed to Q and has edge lengths w(Q) and dQ d(Q). In constant time, we can ?nd a rigid motion ?opt such that ?opt RQ ? rP , and hence ?opt Q ? P , which is optimal. If this is not the case, we sample orientations of P at an interval of ?ε, where ? := 1 w(P ) , 160 min{d(P ), d(Q)}

but omitting all orientations where the angle ? of the spines of P and Q is such that sin ? > 1280?. This results in a set of O(1/ε) orientations of P . For each of these, we compute the optimal translation using Lemma 9, and retain the best rigid motion found as ?app . The running time of this procedure is O((n log n)/ε), and it remains to prove the approximation bound. By Lemma 7, the spines of ?opt P and Q make an 12

angle ? with w(P ) = 1280?, min{d(P ), d(Q)} and so we know that we are sampling an orientation of P at an angle δ from the orientation of ?opt P . sin ? 8 If w(Q) > w(P )/4, then ?= 1 w(P ) 1 w(Q) 1 w(Q) < < , 160 min{d(P ), d(Q)} 40 min{d(P ), d(Q)} 4π min{d(P ), d(Q)}

?ε/2

and so δ ?ε ful?lls the assumption of Lemma 10, implying the approximation bound. If w(Q) w(P )/4, then we have already excluded the case d(Q) We therefore have min{d(P ), d(Q)} > d(P )/2, which implies ?= 1 w(P ) 2 w(P ) < . 160 min{d(P ), d(Q)} 160 d(P ) d(P )/2.

Since δ ?ε/2, the assumptions of Lemma 11 are ful?lled, and the approximation bound follows. Lemma 12 Given two convex polygons P and Q with n vertices in total, and an ε > 0, we can compute a rigid motion ?app such that |?app P ∩ Q| (1 ? ε) max? |?P ∩ Q|, where the maximum is taken over all rigid motions. The running time is O((n log n)/ε).

4

Inner approximations of convex sets

To drastically improve the running time of the algorithm of the previous section, and to apply it to non-polygonal convex sets, we will replace the given convex sets by polygonal approximations whose size depends only on ε. For two sets A and B such that A ? B, the Hausdor?-distance between A and B is dH (A, B) := maxb∈B {mina∈A dist(a, b)}. Given a convex set C, there is a classic inner approximation Pε ? C by Dud√ ley [9] with O(1/ ε) vertices such that the Hausdor?-distance of Pε and C is at most εd(C).√ Ahn et al. [1] showed that Dudley’s method can be implemented in O(TC / ε) time. The bound on the Hausdor?-distance guarantees that C \ Pε is “narrow.” We will need the stronger property that every component of C \ Pε is small in any direction. 13

R εd √ 2 P d

C

d

Fig. 8. Inner approximation of a convex shape.

Lemma 13 Given a convex set C in the plane and ε > 0, one can construct in time O(TC /ε) a convex polygon P ? C with O(1/ε) vertices such that any line intersects C \ P in at most two segments of length at most εd(C).

PROOF. We start by computing an axis-parallel square R circumscribed to C (that is, C touches two opposite sides of R), see Figure 8. This can be done using four extreme point queries. The side length of R is denoted by √ d, and d d(C). We then partition R√ with 2 2/ε equally spaced horizontal and vertical lines at a distance of εd/ 2, compute the intersection points of all these lines with bd(C), and let P be the convex hull of these points. Any connected component of C \ P is contained in a square cell of diameter εd, implying the lemma. 2

While the lemma guarantees a stronger approximation, it needs far more vertices than Dudley’s method. The bound of Θ(1/ε) vertices is tight, however, as can easily be seen by considering the case of a circle. In our second approximation, we return to the Hausdor?-distance, but require that it be less than εw(C) (instead of εd(C) as guaranteed by Dudley’s method). A similar lemma was already proven by Ahn et al. [1] for polygons. We give a proof for arbitrary convex sets C, and a formulation that makes it easy to bound the area of the di?erence C \ P . Lemma 14 Given a convex set C in the plane and ε > 0, one can construct in time O(TC /ε) a convex polygon P ? C with O(1/ε) vertices and a line 14

such that any line parallel to length at most εw(C).

intersects C \ P in at most two segments of

PROOF. We ?rst compute the rectangle R as in Lemma 4. We now use an orthonormal basis where the x-axis is parallel to the longer side of R. The boundary of C consists of two y-monotone chains Cl and Cr . We will select points on these chains to form the set of vertices of P . We select the lowest and highest point (that is, the point with smallest and largest y-coordinate), as well as the leftmost point of Cl and the rightmost point of Cr . We also ensure that any two consecutive vertices of P have vertical distance at most εw(C). This immediately implies that any vertical line intersects C \ P in segments of length at most εw(C). √ By Lemma 4, the √ shorter side of R has length at most 2 2w(C). We can therefore cover R by 2 2/ε horizontal lines equally spaced at distance εw(C). We compute the intersection points of these lines and bd(C), in time O(TC /ε). 2

√ As before, this approximation requires Θ(1/ε) vertices, instead of the Θ(1/ ε) vertices su?cient for Dudley’s method. Again, the bound is tight, as the following lemma shows. Lemma 15 For all integers n > 4, there exists an n-gon Pn such that, for any k-gon Q contained in Pn with dH (Q, Pn ) w(Pn )/5n, we have k (n ? 3)/2.

PROOF. Let vi be the point with coordinates (2i , i), for integers 0 i < n ? 1, let vn?1 = (2n?2 , 0), and let Pn be the convex hull of {vi | 0 i < n}. Note that the width of Pn is less than n?2. We assume that Q ? Pn is a convex k-gon such that dH (Q, Pn ) w(Pn )/5n, so in particular dH (Q, Pn ) < 1/5. For 0 < i < n ? 2, let di denote the distance between the vertex vi and the line segment vi?1 vi+1 . We observe that the distance between vi and the point of the segment vi?1 vi+1 with the same x-coordinate is 1/3. Since the slope of √ vi?1 vi+1 is less than 1, it follows that di is at least 1/(3 2), so di > 1/5. Now suppose that no vertex of Q lies in the interior of some triangle vi?1 vi vi+1 . Then the distance between vi and Q is at least di > 1/5, a contradiction. Therefore, for all 0 < i < n ? 2, there is a vertex of Q in the interior of the triangle vi?1 vi vi+1 . The triangles vi?1 vi vi+1 where i is odd and 0 < i < n ? 2 have disjoint interiors, and there are at least (n ? 3)/2 such triangles, so Q has at least (n ? 3)/2 vertices. 2

15

5

Putting it all together

Our main theorem is the following. Theorem 16 Given two convex sets C1 and C2 in the plane and α > 0, we can compute in time O((TC1 + TC2 )/α + (1/α2 ) log(1/α)) a rigid motion ?app such that the area of ?app C1 ∩ C2 is at least 1 ? α times the maximum over all rigid motions. PROOF. We start by computing circumscribed rectangles Ri for Ci according to Lemma 4, for i = 1, 2. Let di wi be the sides of Ri . By Lemma 4 we have √ d(Ci )/ 2 w(Ci ) di wi d(Ci ), √ 2 2w(Ci ).

√ Let c := 3 2. If d1 cd2 and w1 cw2 , then we use Lemma 4 to compute a homothet r1 of R1 that is contained in C1 and has side lengths d1 /c d2 and w1 /c w2 . In constant time we can ?nd a rigid motion ? such that R2 ? ?r1 . It follows that C2 ? ?C1 , so ? is an optimal solution with value |C2 | = min(|C1 |, |C2 |). We can handle the case where d2 cd1 and w2 cw1 in the same way, so in the following, we assume that (d2 < cd1 or w2 < cw1 ) and (d1 < cd2 or w1 < cw2 ). Without loss of generality, we assume that d2 /w2 d1 /w1 (otherwise we swap C1 and C2 ). This implies that w2 cw1 (if w2 > cw1 then d2 < cd1 , which implies d2 /w2 < d1 /w1 ) and d1 cd2 (if d1 > cd2 then w1 < cw2 , which implies again d2 /w2 < d1 /w1 ). Therefore d1 w2 d2 w1 , d1 w2 cd2 w2 , and d1 w2 d1 cw1 , so d1 w2 c min{d1 , d2 } min{w1 , w2 } √ 2c 2 min{d(C1 ), d(C2 )} min{w(C1 ), w(C2 )}.

Choosing ε = α/(128c + 1), we compute the approximation P1 of Lemma 13 for C1 , the approximation P2 of Lemma 14 for C2 , and then compute the rigid motion ?app of Lemma 12 such that |?app P1 ∩ P2 | (1 ? ε) max |?P1 ∩ P2 |. ?

The total running time is O((TC1 + TC2 )/ε + (1/ε2 ) log(1/ε)), and since α = Θ(ε), it is also O((TC1 + TC2 )/α +(1/α2 ) log(1/α)). So it only remains to prove that this choice of ?app provides the desired approximation. 16

Let ?opt be a rigid motion such that |?opt C1 ∩ C2 | = max |?C1 ∩ C2 |.

?

We will show below that, for any rigid motion ?, |?P1 ∩ P2 | We then have max |?P1 ∩ P2 |

?

|?C1 ∩ C2 | ? 128cε|?opt C1 ∩ C2 |.

(1)

|?opt P1 ∩ P2 | |?opt C1 ∩ C2 | ? 128cε|?opt C1 ∩ C2 |.

By Lemma 12, we have

|?app C1 ∩ C2 |

|?app P1 ∩ P2 | (1 ? ε) max |?P1 ∩ P2 |

?

= max |?P1 ∩ P2 | ? ε max |?P1 ∩ P2 |

? ?

max |?P1 ∩ P2 | ? ε max |?C1 ∩ C2 |

?

= max |?P1 ∩ P2 | ? ε|?

? opt

? opt

C1 ∩ C2 |

|? C1 ∩ C2 | ? 128cε|?opt C1 ∩ C2 | ?ε|?opt C1 ∩ C2 | = |?opt C1 ∩ C2 | ? (128c + 1)ε|?opt C1 ∩ C2 | = (1 ? α)|?opt C1 ∩ C2 |. It remains to prove the claim (1) above for a rigid motion ?. Let D1 := (?C1 \ ?P1 ) ∩ C2 . By Lemma 13, any line parallel to the longer side of R2 intersects D1 in at most two segments of length at most εd(C1 ). Integrating over the shorter side of R2 , we ?nd |D1 | 2εw2 d(C1 ). Let D2 := (C2 \ P2 ) ∩ ?C1 . By Lemma 14, there is a line such that any line parallel to intersects D2 in at most two segments of length at most εw(C2 ) εw2 . Since d(D2 ) d(C1 ), it su?ces to integrate over an interval of length d(C1 ) to obtain |D2 | 2εw2 d(C1 ). Since (?C1 ∩ C2 ) \ (?P1 ∩ P2 ) ? D1 ∪ D2 , we have 17

|(?C1 ∩ C2 ) \ (?P1 ∩ P2 )|

|D1 ∪ D2 |

4εw2 d(C1 ) √ √ 4 2ε2c 2 × min(w(C1 ), w(C2 )) × min(d(C1 ), d(C2 )) 128cε|?opt C1 ∩ C2 |.

|D1 | + |D2 | √ 4 2εd1 w2

The last inequality is due to Lemma 6. This implies |?P1 ∩ P2 | |?C1 ∩ C2 | ? 128cε|?opt C1 ∩ C2 |, completing the proof. 2

6

Translations only

With the same techniques, we can also handle the case where the rigid motion is restricted to be a translation τ . The key idea is to ?rst apply an a?ne transformation that makes C2 fat. Once we have that, we apply the approximation of Lemma 13 to C2 and the approximation of Lemma 14 to C1 . This does not decrease the area of overlap by more than α of the optimum, and so we can ?nally use Lemma 9 on the approximations. The proof is very similar to the proof of Theorem 16. Theorem 17 Given two convex sets C1 and C2 in the plane and α > 0, we can compute in time O((TC1 + TC2 )/α + (1/α) log(1/α)) a translation τ app such that the area of τ app C1 ∩ C2 is at least 1 ? α times the maximum over all translations.

PROOF. We ?rst compute the two rectangles r2 ? C2 ? R2 of Lemma 4. There is an a?ne transformation f that maps r2 to the unit square. Since f preserves area ratios, our problem is equivalent to ?nding an approximate maximum overlap of f (C1 ) and f (C2 ) under translation. So in the remainder of this proof, we will assume, without loss of generality, that r2 ? C2 ? R2 where √ r2 is the unit square and R2 is an axis–parallel square with side length 3 2. We now compute the two homothetic rectangles r1 ? C1 ? R1 of Lemma 4. We denote by w1 d1 the lengths of the sides of R1 . √ If d1 1/ 2, then we can ?nd in constant time a translation τ such that τ R1 ? r2 . Therefore τ C√? C2 , and we can choose τ app = τ . So from now on 1 √ we assume that d1 > 1/ 2, which implies d(C1 ) > 1/ 2. √ On the other√ hand, suppose that w1 18 2. Then the shorter side of r1 has length w1 /(3 2) 6. So we can ?nd in constant time a translation τ such 18

that R2 ? τ r1 . Therefore C2 ? τ C1 , √ we can again choose τ app = τ . So and √ from now on we assume that w1 < 18 2, which implies w(C1 ) < 18 2. √ We ?x ε = α/(432 2). We apply Lemma 14 to C1 , so we obtain an ε– approximating polygon P1 . We apply Lemma 13 to C2 and obtain an ε– approximating polygon P2 . Notice that until now we have spent only O((TC1 + TC2 )/α) time. Now we apply Lemma 9 and ?nd the translation τ app that maximizes |τ app P1 ∩ P2 |. This takes time O((1/α) log(1/α)). Let τ opt be a rigid motion such that |τ opt C1 ∩ C2 | = max |τ C1 ∩ C2 |.

τ

We will show below that, for any translation τ , |τ P1 ∩ P2 | We then have |τ app C1 ∩ C2 | |τ app P1 ∩ P2 | |τ opt P1 ∩ P2 | |τ opt C1 ∩ C2 | ? α|τ opt C1 ∩ C2 |, |τ C1 ∩ C2 | ? α|τ opt C1 ∩ C2 |. (2)

and thus we proved that τ app provides the desired approximation. It remains to prove Claim (2). By Lemma 5, C1 contains a rectangle r with √ sides d(C1 )/2 and w(C1 )/4. If w(C1 ) 4 2, then both sides of r have length √ at least 2, and so there is a translation that maps r such that it covers r2 . This implies that |τ opt C1 ∩ C2 | |r2 | = 1 w(C1 ) √ . 18 2

√ If, on the other hand, w(C1 ) < 4 2, then we consider a smaller rectangle r √ with sides 1/2 2 √ w(C1 )/8 contained in r. Since both sides of r have and length at most 1/ 2, there is a translation that maps r inside r2 , which implies again that |τ opt C1 ∩ C2 | w(C1 ) w(C1 ) 1 > √ |r | = √ × 8 2 2 18 2 (3)

Let D1 := (τ C1 \ τ P1 ) ∩ C2 . By Lemma 14, there is a line such that any line parallel to intersects τ C1 \ τ P1 in at most two segments of length at most εw(C1 ). Since d(C2 ) 6, it su?ces to integrate over an interval of length d(C2 ) to obtain |D1 | 12εw(C1 ). Let D2 := (C2 \ P2 ) ∩ τ C1 . Let R be a bounding rectangle of τ C1 with one side length equal to w(C1 ). By Lemma 13, any line parallel to the longer side 19

of R intersects D1 in at most two segments of length at most εd(C2 ) Integrating over the shorter side of R, we ?nd |D2 | 12εw(C1 ). Since (τ C1 ∩ C2 ) \ (τ P1 ∩ P2 ) ? D1 ∪ D2 , we have |(τ C1 ∩ C2 ) \ (τ P1 ∩ P2 )| By Equation (3), it yields |(τ C1 ∩ C2 ) \ (τ P1 ∩ P2 )| which completes the proof of Claim (2). 2 α|τ opt C1 ∩ C2 |, |D1 ∪ D2 | 24εw(C1 ).

6ε.

7

Acknowledgments

We would like to thank Peter Brass for helpful discussions.

References

[1] H.-K. Ahn, P. Brass, O. Cheong, H.-S. Na, C.-S. Shin, and A. Vigneron. Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets. Comput. Geom. Theory Appl., in press. [2] H. Alt, J. Bl¨mer, M. Godau, and H. Wagener. Approximation of convex o polygons, Proc. 17th Internat. Colloq. Automata Lang. Program., Lecture Notes Comput. Sci. 443, p. 703–716, 1990. [3] D. Avis, P. Bose, G. Toussaint, T. Shermer, B. Zhu, J. Snoeyink. On the sectional area of convex polytopes, Proc. 12th ACM Symp. Comput. geometry, (1996) 411–412. [4] H. Alt, U. Fuchs, G. Rote, and G. Weber. Matching convex shapes with respect to the symmetric di?erence. Algorithmica, 21:89–103, 1998. [5] M. de Berg, S. Cabello, P. Giannopoulos, C. Knauer, R. van Oostrum, and R. C. Veltkamp. Maximizing the area of overlap of two unions of disks under rigid motion. In Scandinavian Workshop on Algorithm Theory, Lecture Notes Comput. Sci. 3111, p. 138–149, 2004. [6] M. de Berg, O. Cheong, O. Devillers, M. van Kreveld, and M. Teillaud. Computing the maximum overlap of two convex polygons under translations. Theory of Computing Systems, 31:613–628, 1998. [7] O. Cheong, S. Har-Peled, and A. Efrat. On ?nding a guard that sees most and a shop that sells most, Proc. 15th ACM-SIAM Symp. Discrete Algorithms, (2004) 1098–1107.

20

[8] M. Dickerson and D. Scharstein. Optimal placement of convex polygons to maximize point containment. Comput. Geom. Theory Appl. 11 (1998) 1–16. [9] R. M. Dudley. Metric entropy of some classes of sets with di?erentiable boundaries, J. Approximation Theory 10 (1974) 227–236; Erratum in J. Approx. Theory 26 (1979) 192–193. [10] D. M. Mount, R. Silverman, and A. Y. Wu. On the area of overlap of translated polygons. Computer Vision and Image Understanding: CVIU, 64(1):53–61, 1996. [11] O. Schwarzkopf, U. Fuchs, G. Rote, E. Welzl. Approximation of convex ?gures by pairs of rectangles, Comput. Geom. Theory Appl. 10 (1998) 77–87; also in STACS 1990, LNCS 415, p. 240–249. [12] G. T. Toussaint. Solving geometric problems with the rotating calipers, Proc. IEEE MELECON, Athens, Greece, 1983, p. 1–4..

21