Geometric dilation of closed planar curves: a new lower bound

Geometric dilation of closed planar curves: A new lower bound Annette Ebbers-Baumann a, Ansgar Gr¨une a, and Rolf Klein a aDept. of Computer Science I, University of Bonn, D - 53117 Bonn, Germany Abstract Given any simple closed curve Cin the Euclidean plane, let wand Ddenote the minimal and the maximal caliper distances of C, correspondingly. We show that any such curve Chas a geometric dilation of at least arcsin( w D) + p(w D)2 −1. Key words: computational geometry, convex geometry, convex curves, dilation, detour, lower bound 1. Introduction Let Cbe a simple closed curve Cin the Euclidean plane. For any two points, pand q, on C let π(p, q) denote the shorter of the two curve segments of Cthat connects pwith q. Then the geometric dilation, δ(C), of Cis defined as δ(C) := sup p,q∈C,p6=q |π(p, q)| |pq|(1) The computation of the geometric dilation (then called detour) was first studied in [5], where an O(nlog n) approximation algorithm for polygonal chains in the plane was given. Further efficient algorithms to compute the geometric dilation of certain classes of curves and networks were presented in [1], [11], and [9]. The question of embedding a finite point set in the plane into a network with low geometric dilation was recently studied in [4]. There it has been shown that any simple closed planar curve has dilation δ(C)≥π/2, using Cauchy’s surface area formula. Note, that the analogue concept on graphs, where only the point set of the vertices is taken into account for computing the dilation, was extensively studied under the notion of spanners and low dilation graphs, see e.g. [7] for a survey and [3], [2] for recent results. However, there are Email addresses: [email protected] (Annette Ebbers-Baumann), [email protected] (Ansgar Gr¨une), [email protected] (Rolf Klein). structural differences between the two concepts, as already mentioned e.g. in [5]. In this paper we prove a powerful generalization of the lower bound from [4]. Namely, let wand D denote the width and the diameter of the convex hull of C, correspondingly, that is, the minimal and the maximal distances of a rotating caliper measuring C; see Figure 1. C D w Fig. 1. Diameter Dand width wof ch(C). Then, δ(C)≥arcsin w D+rw D2−1 (2) holds for the geometric dilation of C. This lower bound has a minimum value of π/2 if and only if w=Dholds. (Note, however, that the circle is not the only closed curve satisfying w=D.) The proof of formula (2) uses a well-known transformation of convex curves called the central symmetrization, see e.g. [6] and [10]. The rest of this paper is organized as follows. In Section 2 we give some necessary definitions and 20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry basic lemmata. Then, in Section 3 we cite the symmetrization transformation. Finally, Section 4 contains the proof of our lower bound. 2. Definitions and basic properties Throughout this paper we consider simple planar cycles C, i.e. closed curves in the Euclidean plane without self-intersections. A simple cycle C is convex iff it always turns into the same direction, that is, iff Chas a convex interior domain. Definition 1 (Dilation) Let Cbe a simple cycle, and let p, q ∈Cbe two points on C. (i) Cq pdenotes one of the two possible sub-paths of Cconnecting pand q, characterized by its turning direction: If one moves from pto qon Cq p, one turns anti-clockwise (C=Cq p∪Cp q). (ii) The dilation of a pair of points (p, q)∈ C×Cis the length of a shortest sub-path πC(p, q)of Cconnecting pand q,|πC(p, q)|= min(Cq p,Cp q), divided by its Euclidean distance, i.e. δC(p, q) := |πC(p,q)| |pq|. (iii) The geometric dilation of Cis the supremum of the dilation values of all pairs of points of C, i.e. δ(C) := supp,q∈C,p6=qδC(p, q). By continuity and compactness arguments one can show that every finite convex curve has a pair of points attaining maximum dilation. Definition 2 (Partition Pair) Let p∈Cbe a point on a cycle C. Then the unique partition partner ˆpof pis characterized by |πC(p, ˆp)|=|C|/2. We say that (p, ˆp)is a partition pair of C. By continuity arguments it is easy to show that for every direction v∈S1there exists a partition pair (p, ˆp), i.e. ˆp−p=|ˆp−p|v. Definition 3 (Breadths) Let Cbe a simple cycle, and let v∈S1be an arbitrary direction. (i) The v-length of Cis the maximum distance of a pair of points with direction v, i.e. lC(v) := max {|pq| | p, q ∈C, q −p=|q−p|v}. (ii) The v-width (v-breadth) of Cis the distance of the two supporting lines of Cperpendicular to v, i.e. wC(v) := maxp∈Cp·v−minp∈Cp·v. (iii) The v-partition pair distance,hC(v), of Cis the distance of the partition pair with direction v. (iv) The diameter, D(C), of Cis the maximal v-length, i.e. D(C) := maxv∈S1lC(v). The width, w(C), of Cis the minimal v-length, i.e. w(C) := minv∈S1lC(v). (v) The maximal partition pair distance is denoted by H(C) := maxv∈S1hC(v)and the minimal partition pair distance by h(C) := minv∈S1hC(v). l(v) w(v) v h(v) C Fig. 2. Three different breadth measures. As used in the introduction, width and diameter can also be defined using the v-width values which is proved in [8], [12] respectively: Lemma 4 Let Cbe a simple cycle, then D(C) = maxv∈S1wC(v). If Cis convex, then w(C) = minv∈S1wC(v). The next statement follows immediately from the definitions; see Figure 2. Lemma 5 Let Cbe a simple convex cycle, and let v∈S1be an arbitrary direction. Then the following inequalities hold: hC(v)≤lC(v)≤wC(v). 3. Central symmetrization The central symmetrization (see e.g. [6], [8], [10]) is a well-known transformation which maps any convex cycle to a convex point-symmetric cycle. In our notion, the central symmetrization is based on the length values lC(v), introduced in Definition 3(i). Amazingly, it preserves all the width values wC(v). And Cauchy’s surface area formula implies that the perimeter is not changed either. Definition 6 Let Cbe a convex cycle. The central symmetrization of Cis the cycle C′given by the parametrization c′:S1→R2,c′(v) := lC(v) 2v. As depicted in Figure 3, we can construct the central symmetrization by translating all the centers of the segments of maximal length connecting pairs of points on Cto the origin. However, there is an easier and more helpful construction, described in the following lemma. March 25-26, 2004 Seville (Spain) C C’ Fig. 3. The central symmetrization of an isosceles right-angled triangle. Lemma 7 Let X:= f(C)∪Cbe the face bounded by Cincluding Citself. Then define a set X′to be the arithmetic mean of Xand −X; see [10]. It is the Minkowski sum X⊕−Xscaled by 1/2. Then, the central symmetrization C′is the boundary of this arithmetic mean X′: X:= f(C)∪C X′:= 1 2(X⊕−X)) = 1 2(u−v) u, v ∈X ⇒C′=∂X′ PROOF. The proof that this second way of constructing C′is also correct is straightforward. Let v∈S1be an arbitrary direction. Define l:= sup{c∈R>0|cv ∈X′}. Then due to X′being closed, lv is an element of X′. And for k > l the point kv is not in X′. Thus, lv ∈∂X′. It also follows that there are p, q ∈Xsuch that lv = (1/2)(q−p). On the other hand, the definition of lyields that k > l implies there are no p, q ∈X satisfying kv = (1/2)(q−p). Thus, l= (1/2)lC(v). Hence, our analysis results in the following parametrization of ∂X′:c′(v) = (1/2)lC(v)v. And this is exactly the parametrization we used to define C′. The following lemma, stated here without proof, lists the most important properties of the central symmetrization. The fact that the width values are preserved is mentioned without proof in [6]. Gritzmann and Klee [8] prove the width-preserving and length-preserving property. The statement that the perimeter is preserved is also proved in [10]. Lemma 8 Let Cbe a simple convex cycle, and let C′be its central symmetrization. Then, the cycle C′has the following properties: (i) Cycle C′is convex. (ii) Cycle C′is point-symmetric with respect to the origin. (iii) For every direction v∈S1,hC′(v) = lC′(v) = lC(v)≥hC(v), and wC′(v) = wC(v). (iv) Width, diameter and perimeter are preserved by central symmetrization, i.e. w(C′) = w(C),D(C′) = D(C)and |C′|=|C|. Because we can show that the dilation of a convex cycle is always attained by a partition pair, it follows easily from those properties that the dilation of the transformed cycle cannot be larger then the original one: Lemma 9 The dilation of C′is not larger than the original dilation, i.e. δ(C′)≤δ(C). 4. The lower bound To apply the transformation described in Section 3, we need the fact that the dilation of the boundary of the convex hull of any planar cycle Cis at most the dilation of Citself. Due to space limitations we state this here without proof. Theorem 10 Let C⊂ R 2be a simple closed curve. Let ∂ch(C)denote the boundary of the convex hull of C. Then holds δ(C)≥δ(∂ch(C)). Now we prove our result on the lower bound, using the central symmetrization transformation. Theorem 11 Let C⊂ R 2be a simple closed curve. Let wbe the width and let Dbe the diameter of ch(C), the convex hull of C. Then the dilation of Cis bounded from below by δ(C)≥arcsin w D+sD w2 −1. q c R α r x p B (c) r Fig. 4. The shortest cycle not intersecting the disk Br(c). PROOF. Because of Theorem 10 we can assume w.l.o.g. that Cis convex. To show the main idea of the proof we first consider a point-symmetric cycle ˜ C⊂ R 2with center-point c, see Figure 4. Then, obviously, the partition pairs are also pointsymmetric with respect to c. Let (p, q) be a parti- 20th European Workshop on Computational Geometry tion pair having maximum distance |pq|=H(˜ C). We define R:= H(˜ C)/2. Let Br(c) be the open disc with center point c and radius r:= h(˜ C)/2, that is Br(c) := {b∈ R 2||b−c|< r}. Then ˜ Ccannot intersect with Br(c), otherwise there would exist a partition pair having a distance smaller than h(˜ C) = 2r. By using the shortest possible cyclic path connecting pand qin the Euclidean plane, not intersecting Br(c) but enclosing it, we obtain a curve ˜ CminP er, as shown in Figure 4. By construction ˜ CminP er is the point-symmetric curve of smallest perimeter that has minimum partition pair distance h(˜ C) and maximum partition pair distance H(˜ C). Due to symmetry reasons this perimeter is P= 4x+ 4rα, with xdenoting the lengths of the straight path segments from pand qto the tangent points on Br(c), correspondingly, and rα the lengths of the path segments on ∂Br(c). Using Pythagoras we get x=√R2−r2. And by considering the angles in the rectangular triangle, we obtain sin α= cos(π 2−α) = r R. Because the maximum dilation of the convex cycle ˜ Cis attained by a partition pair having shortest path distance ˜ P 2≥P 2, it holds: δ(˜ C)≥ P 2 2r=4x+ 4rα 4r=√R2−r2 r+ arcsin r R =sR r2 −1 + arcsin r R(3) Now, let Cbe an arbitrary convex cycle, and let C′be its central symmetrization. Then, Lemma 9 yields that δ(C)≥δ(C′). And by Lemma 8(iv) we know that width and diameter are preserved, i.e. w(C′) = w(C) and D(C′) = D(C). However, in a point-symmetric convex cycle v-length and vpartition pair distance are equal, implying w(C′) = h(C′) and D(C′) = H(C′). Thus, if we apply formula (3) to C′keeping in mind that r=h(C′)/2 = w(C′)/2 = w(C)/2 = w/2 and R=H(C′)/2 = D(C′)/2 = D(C)/2 = D/2, we get: δ(C)≥sD w2 −1 + arcsin w D This lower bound equals the global lower bound of π 2shown in [4] only for curves of constant width (w=D). Further arguments show that the inequality gets strict if Cis not point-symmetric or not convex. Hence, only circles have dilation π 2. Remark 12 By replacing lC(v)by hC(v)in Definition 3 we get a new transformation, the partition pair transformation. Ideas analogous to the ones presented here show that δ(C)≥sH h2 −1 + arcsin h H where H=H(ch(C)) and h=h(ch(C)) for every simple cycle C. References [1] P. Agarwal, R. Klein, Ch. Knauer, and M. Sharir. Computing the detour of polygonal curves. Tech. Report B 02-03, FU Berlin, 2002. [2] P. Bose, J. Gudmundsson, and M. Smid. Constructing plane spanners of bounded degree and low weight. In Proc. 10th Europ. Symp. Algo., LNCS 2461:234–246, 2002. [3] D.Z. Chen, G. Das, and M. Smid. Lower bounds for computing geometric spanners and approximate shortest paths. Discr. Appl. Math., 110:151–167, 2001. [4] A. Ebbers-Baumann, A. Gr¨une, and R. Klein. On the geometric dilation of finite point sets. In Proc. 14th Internat. Symp. Algo. and Comput., LNCS 2906:250– 259, 2003. [5] A. Ebbers-Baumann, R. Klein, E. Langetepe, and A. Lingas. A fast algorithm for approximating the detour of a polygonal chain. In Proc. 9th Europ. Symp. Algo., LNCS 2161:321–332, 2001. [6] H.G. Eggleston. Convexity, Cambridge University Press, 1958. [7] D. Eppstein. Spanning trees and spanners. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pp. 425–461. Elsevier, 1999. [8] P. Gritzmann and V. Klee. Inner and outer j-radii of convex bodies in finite-dimensional normed spaces. Discrete Comput. Geom., 7:255–280, 1992. [9] Ansgar Gr¨une, Rolf Klein, and Elmar Langetepe. Computing the detour of polygons. In Abstracts 19th European Workshop Comput. Geom., pages 61–64. University of Bonn, 2003. [10] I.M. Jaglom and W.G. Boltjanski. Konvexe Figuren, VEB Deutscher Verlag der Wissenschaften, 1956. [11] S. Langerman, P. Morin, and M. Soss. Computing the maximum detour and spanning ratio of planar chains, trees and cycles. In Proc. 19th Internat. Symp. Theor. Aspects of C.Sc., LNCS 2285:250–261, 2002. [12] S.R. Lay. Convex Sets and their Applications, John Wiley & Sons, 1982.