{'fraction_non_alphanumeric': 0.05385067095848105, 'fraction_numerical': 0.0182692098566737, 'mean_word_length': 3.819706498951782, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the geometric dilation of closed curves, graphs, and point sets

The detour between two points u and v (on edges or vertices) of an embedded planar graph whose edges are curves is the ratio between the shortest path in in the graph between u and v and their Euclidean distance. The maximum detour over all pairs of points is called the geometric dilation. Ebbers-Baumann, Gruene and Klein have shown that every finite point set is contained in a planar graph whose geometric dilation is at most 1.678, and some point sets require graphs with dilation at least pi/2 = 1.57... We prove a stronger lower bound of 1.00000000001*pi/2 by relating graphs with small dilation to a problem of packing and covering the plane by circular disks. The proof relies on halving pairs, pairs of points dividing a given closed curve C in two parts of equal length, and their minimum and maximum distances h and H. Additionally, we analyze curves of constant halving distance (h=H), examine the relation of h to other geometric quantities and prove some new dilation bounds.


Introduction
Consider a planar graph G embedded in Ê 2 , whose edges are curves 1 that do not intersect.
Such graphs arise naturally in the study of transportation networks, like waterways, railroads or streets. For two points, p and q (on edges or vertices) of G, the detour between p and q in G is defined as where d G (p, q) is the shortest path length in G between p and q, and |pq| denotes the Euclidean distance, see Figure 1a for an illustration. Good transportation networks should have small detour values. In a railroad system, access is only possible at stations, the vertices of the graph. Hence, to measure the quality of such networks, we can take the maximum detour over all pairs of vertices. This results in the well-known concept of graph-theoretic dilation studied extensively in the literature on spanners, see [11] for a survey.
However, if we consider a system of urban streets, houses are usually spread everywhere along the streets. Hence, we have to take into account not only the vertices of the graph but all the points on its edges. The resulting supremum value is the geometric dilation δ(G) := sup p,q∈G δ G (p, q) = sup p,q∈G d G (p, q) |pq| on which we concentrate in this article. Several papers [10,17,2] have shown how to efficiently compute the geometric dilation of polygonal curves. Besides this the geometric dilation was studied in differential geometry and knot theory under the notion of distortion, see e.g. [13,16]. Figure 2: A section of the grid from [8] which has small dilation, less than 1.678.
Ebbers-Baumann et al. [8] recently considered the problem of constructing a graph of lowest possible geometric dilation containing a given finite point set on its edges. Even for three given points this is not a trivial task. For some examples, clearly a Steiner-tree with three straight line segments is optimal. In other cases a path consisting of straight and curved pieces is better, but it is not easy to prove its optimality. The infimum is taken over all embedded planar graphs G with a finite number of vertices, where the edges may be curves like discussed above. For example, a scaled hexagonal grid can clearly be used to embed any finite subset of É × √ 3É like the example in Figure 1b. The geometric dilation √ 3 ≈ 1.732 of this grid is attained between two midpoints of opposite edges of a hexagon. Figure 2 and proved that its dilation is less than 1.678. They showed that a slightly perturbed version of the grid can be used to embed any finite point set. Thereby they proved ∆ < 1.678.

Ebbers-Baumann et al. introduced the improved grid shown in
They also derived that ∆ ≥ π/2, by showing that a graph G has to contain a cycle to embed a certain point set P 5 with low dilation, and by using that the dilation of every closed curve 2 C is bounded by δ(C) ≥ π/2. They conjectured that this lower bound is not tight. It is known that circles are the only cycles of dilation π/2, see [9,Corollary 23], [1,Corollary 3.3], [16], [13]. And intuition suggests that one cannot embed complicated point sets with dilation π/2 because every face of the graph would have to be a circular disk. This idea would have to be formalized and still does not rule out that every point set could be embedded with dilation arbitrarily close to π/2. Therefore, we need the result presented in Section 4. We show that cycles with dilation close to π/2 are close to circles, in some well-defined sense (Lemma 6). The lemma can be seen as an instance of a stability result for the geometric inequality δ(C) ≥ π/2, see [12] for a survey. Such results complement geometric inequalities (like the isoperimetric inequality between the area and the perimeter of a planar region) with statements of the following kind: When the inequality is fulfilled "almost" as an equation, the object under investigation is "close" to the object or class of objects for which the inequality is tight. An important idea in the proof of this stability result is the decomposition of any closed curve C into the two cycles C * and M defined in Section 3.
In Section 5 we use Lemma 6 to relate the dilation problem to a certain problem of packing and covering the plane by disks. By this we prove our main result ∆ ≥ (1 + 10 −11 )π/2. The proof also relies on the notion of halving pairs and their distance, the halving distance, introduced by Ebbers-Baumann et al. [9] to facilitate the dilation analysis of closed curves.
In Section 6 we analyze curves of constant halving distance, an analog to the well-known curves of constant width. Understanding curves of constant halving distance and their properties is a key point in designing networks with small geometric dilation. For example, the grid structure in Figure 1b is constructed by replicating such a curve at each vertex of a regular hexagonal grid, thereby improving the dilation from √ 3 ≈ 1.732 to 1.678. Curves of constant halving distance were already discovered in 1921 [22] 3 , and, as we will explain, they are related to other interesting geometric notions, such as curves of constant width and Stanis law Ulam's Floating Body Problem.
From the viewpoint of convex geometry it is interesting to consider the relations of the minimum and maximum halving distance, h and H, to other geometric quantities of a given convex closed curve C. In Section 7 we give first results in this direction.
In Section 8 we use some of them to derive a new upper bound on the geometric dilation of closed convex curves. We also prove several new dilation bounds for polygons.

Basic Definitions and Properties
An important special case of the planar graphs embedded in Ê 2 are simple 4 closed curves or cycles for short. Let C be such a closed curve. By |C| we denote its length. Shortest path distance d C (p, q), detour δ C (p, q) and geometric dilation δ(C) are defined like in the case of arbitrary graphs. Often we will use a bijective arc-length-parameterization c : [0, |C|) → C. This implies d C (c(s), c(t)) = min (|t − s|, |C| − |t − s|), and |ċ(t)| = 1 wherever the derivative exists.
Consider Figure 3. Two points p = c(t) andp = c(t + |C|/2) on C that divide the length 3 We would like to thank Salvador Segura-Gomis for pointing this out. 4 A curve is called simple if it has no self-intersections.
of C in two equal parts form a halving pair of C. Here and later on, t + |C|/2 is calculated modulo |C|. The segment which connects p andp is a halving chord, and its length is the corresponding halving distance. We write h = h(C) and H = H(C) for the minimum and maximum halving distance of C. Furthermore, we will consider the diameter D := max{|pq|, p, q ∈ C} of a closed curve C and the width w of a convex cycle C which is the minimum distance of two parallel lines enclosing C.
The main link between dilation and halving distance is the inequality which follows immediately from the definitions because the right-hand side equals the detour of a halving pair of minimal distance h. If C is convex, equality is attained.

Midpoint Curve and Halving Pair Transformation
Let C be a closed curve and let c(t) be an arc-length parameterization. The two curves derived from C illustrated in Figure 4 turn out to be very useful for both, proving the stability result in Section 4 and analyzing the curves of constant halving distance in Section 6. The midpoint curve M is formed by the midpoints of the halving chords of C, and is given by the parameterization Figure 4: An equilateral triangle C, and the two curves C * and M derived from C.
The second curve C * is the result of the halving pair transformation introduced in [9]. It is obtained by translating all the halving chords so that their midpoints are located in the origin. Then, C * is the curve described by the endpoints of these translated chords. This results in the parameterization Note that c * (t) is half the vector connecting the corresponding halving pair. By definition, c * (t) = −c * (t + |C|/2), hence C * is centrally symmetric. The curve C * has the same set of halving distances as C; thus, h(C * ) = h(C) = h and H(C * ) = H(C) = H. Furthermore, it is contained in an (H/h)-ring, see Figure 4. An η-ring is the closed region between two concentric circles where the outer radius equals η times the inner radius.
The parameterization of the midpoint curve satisfies m(t) = m(t + |C|/2), and thus, M traverses the same curve twice when C and C * are traversed once. We define |M | as the length of the curve m(t) corresponding to one traversal, i.e., the parameter interval is [0, |C|/2].
The halving pair transformation decomposes the curve C into two components, from which C can be reconstructed: This is analogous to the decomposition of a function into an even and an odd function, or writing a matrix as a sum of a symmetric and a skew-symmetric matrix.
A key fact in the proof of our main result, Theorem 2, is the following lemma, which we think is of independent interest. It provides an upper bound on the length |M | of the midpoint curve in terms of |C| and |C * |.
Proof. As mentioned in the introduction, we assume that C is piecewise continuously differentiable. However, the following proof can be extended to arbitrary rectifiable curves (i.e., curves with finite length).
Using the linearity of the scalar product and |ċ(t)| = 1, we obtain This means that the derivative vectorsċ * (t) andṁ(t) are always orthogonal, thus (4) yields This implies The above inequality -from which the lemma follows -can be seen by a geometric argument: the left integral

Stability Result for Closed Curves
In this section, we prove that a simple closed curve C of low dilation (close to π/2) is close to being a circle. To this end, we first show that C * is close to a circle, i.e. H/h is close to 1. Then, we prove that the length of the midpoint curve is small. Combining both statements yields the desired result.
We use the following lemma to find an upper bound on the ratio H/h. It extends an inequality of Ebbers-Baumann et al. [9,Theorem 22] to non-convex cycles.

Lemma 3
The geometric dilation δ(C) of any closed curve C satisfies This bound is tight. The function g(x) = arcsin 1/x + √ x 2 − 1 on the right side is displayed in Figure 5b. It starts from g(1) = π/2 and is increasing on [1, ∞). This shows that a cycle C of small dilation has a ratio H/h close to 1.
Proof. From the definition of dilation and halving pairs and Corollary 1, we get We have seen above that h(C * ) = h(C) = h and H(C * ) = H(C) = H. Then, by the symmetry of C * , any two points p and −p on C * form a halving pair of distance 2 |p| ≥ h. Hence, C * contains the disk B h/2 (0) of radius h/2 around the origin. On the other hand, C * has to connect some halving pair (q, −q) of maximum distance H. Therefore, C * has at least the length of the curveĈ depicted in Figure 5. Basic trigonometry yields which completes the proof. Kubota [14] used similar arguments to prove that the length of any convex closed curve C of width w and diameter D satisfies |C| ≥ 2w arcsin(w/D) + 2 √ D 2 − w 2 . Here and in the dilation bound, equality is attained byĈ.
In order to prove that a closed curve of small dilation lies in a thin ring, we still need an upper bound on the length |M | of the midpoint cycle. We achieve it by using Lemma 2.
Proof. By the assumption and because the dilation of C is at least the detour of a halving pair attaining minimum distance h, we have (1 + ε)π/2 ≥ δ(C) (1) ≥ |C|/2h, implying As seen before, C * encircles but does not enter the open disk B h/2 (0) of radius h/2 centered at the origin 0. It follows that the length of C * is at least the perimeter of B h/2 (0): By plugging everything together, we get which concludes the proof of Lemma 4.
Intuitively it is clear (remember the definitions (2), (3) and Figure 4) that the upper bound on H/h from Lemma 3 and the upper bound on |M | of Lemma 4 imply that the curve C is contained in a thin ring, if its dilation is close to π 2 . This is the idea behind Lemma 6, the main result of this section. To prove it, we will apply the following well-known fact, see e.g. [19], to M .

Lemma 5
Every closed curve C can be enclosed in a circle of radius |C|/4.
Proof. Fix a halving pair (p,p) of C. Then by definition, for any q ∈ C, we have |pq|+|qp| ≤ d C (p, q) + d C (q,p) = d C (p,p) = |C|/2. It follows that C is contained in an ellipse with foci p andp and major axis |C|/2. This ellipse is included in a circle with radius |C|/4, and the lemma follows.
Proof. By Lemma 5, the midpoint cycle M can be enclosed in a circle of radius |M |/4 and some center z. By the triangle inequality, we immediately obtain Thus, C can be enclosed in the ring between two concentric circles with radii R = H/2 + |M |/4 and r = h/2 − |M |/4 centered at z. To finish the proof, we have to bound the ratio R/r. For simplicity, we prove only the asymptotic bound R/r ≤ 1 + O( √ ε). The proof of the precise bound, which includes all numerical estimates, is given in Appendix A.
Assume H/h = (1 + β). Lemma 3 and power series expansion yield the approximate lower bound With our initial assumption δ(C) completing the proof of the asymptotic bound in Lemma 6.
The lemma can be extended to a larger, more practical range of ε, by increasing the coefficient of √ ε.
Tightness of the bound in Lemma 6. The curve C defined by the parameterization ϕ C 1 0  Figure 6 shows that the order of magnitude in the bound cannot be improved. Note that c(ϕ) is not an arc-length parameterization.

c(ϕ) below and illustrated in
This curve is the path of a moon moving around the earth on a small elliptic orbit with major axis 2s (collinear to the line earth-sun), with a frequency three times that of the earth's own circular orbit around the sun.
Here, we only sketch how to bound the dilation and halving distances of this curve. The details are given in Appendix B. A ring with outer radius R and inner radius r containing the curve satisfies R/r ≥ (1 + s)/(1 − s) = 1 + Θ(s). One can show that the length is bounded by |C| ≤ 2π + O(s 2 ), and the halving distances are bounded by If s is not too large, C is convex, and this implies by Lemma 1 that the dilation is given by Thus, we have dilation δ = (1 + ε)π/2 with ε = O(s 2 ), but the ratio of the radii of the enclosing ring is 1 + Θ(s) = 1 + Ω( √ ε). A more careful estimate shows that this ratio is . Thus, the coefficient 3 in Lemma 6 cannot be improved very much.

Improved Lower Bound on the Dilation of Finite Point Sets
We now combine Lemma 6 with a disk packing result to achieve the desired new lower bound on ∆. A (finite or infinite) set D of disks in the plane with disjoint interiors is called a packing.
Theorem 1 (Kuperberg, Kuperberg, Matoušek and Valtr [15]) Let D be a packing in the plane with circular disks of radius at most 1. Consider the set of disks D ′ in which each disk D ∈ D is enlarged by a factor of Λ = 1.00001 from its center. Then D ′ covers no square with side length 4.
There seems to be an overlooked case in the proof of this theorem given in [15]. (Using the terminology of [15], one of the conditions that needs to be checked in order to ensure that R n+1 is contained in R n has been forgotten, see for example the disk D in Figure 11 of [15].) We think that the proof can be fixed, and moreover, the result can be proved for values somewhat larger than 1.00001, as the authors did not try to optimize the constant Λ. However, the case distinctions are very delicate, and we have not fully worked out the details yet. For these reasons, we state our main result depending on the value Λ.
Proof. We first give an overview of the proof, and present the details afterwards. Consider the set P := { (x, y) | x, y ∈ {−9, −8, . . . , 9} } of grid points with integer coordinates in the square Q 1 := [−9, 9] 2 ⊂ Ê 2 , see Figure 7. We use a proof by contradiction and assume that there exists a planar connected graph G that contains P (as vertices or on its edges) and satisfies δ(G) < ∆(Λ). The idea of the proof is to show that if G attains such a low dilation, it contains a collection M of cycles with disjoint interiors which cover the We will choose M in such a way that the dilation of every cycle C ∈ M will be bounded by δ(C) ≤ δ(G) ≤ ∆(Λ). The function ∆(Λ) is defined so that we can easily apply Lemma 6 to this situation. In particular, Λ ≤ 1.03 guarantees ∆(Λ) ≤ 1.0001π/2. We derive that every C has to be contained in a Λ-ring. As by Claim 1 the length of each cycle C ∈ M will be bounded by 8π, the inner disks of these rings have a radius r ≤ 4. This is a contradiction to Theorem 1 (situation scaled by 4) because the inner disks of the rings are disjoint and their Λ-enlargements cover Q 2 .
We would like to use the cycles bounding the faces of G for M. Indeed, δ(G) < ∆(Λ) < 2 implies that they cover Q 2 , see Claim 1 below. However, their dilation could be bigger than the dilation δ(G) of the graph, see Figure 8b. There could be shortcuts in the exterior of C, i.e., the shortest path between p, q ∈ C does not necessarily use C.
Therefore, we have to find a different class of disjoint cycles covering Q 2 which do not allow shortcuts. The idea is to consider for every point x in Q 2 the shortest cycle of G such that x is contained in the open region bounded by the cycle. These cycles are non-crossing, that is, their enclosed open regions are either disjoint or one region contains the other (Claim 4). If we define M to contain only the cycles of C which are maximal with respect to inclusion of their regions, it provides all the properties we need. We now present the proof in detail.
Proof. We consider an arbitrary point x ∈ Q 2 and a grid square S which contains x like shown in Figure 7b. For every pair p, q of neighboring grid points of P , let ξ(p, q) be a shortest path in G connecting p and q. The length of each such path ξ(p, q) is bounded by |ξ(p, q)| ≤ δ G (p, q) · 1 < 2. Consider the closed curve C obtained by concatenating the 12 shortest paths between adjacent grid points on the boundary of the 3 × 3 square around S. None of the shortest paths can enter S because this would require a length bigger than 2. Therefore C encloses but does not enter S, thus it also encloses x ∈ S. The total length of C is bounded by |C| ≤ 12 · δ(G) ≤ 12∆(Λ) ≤ 12 · 1.0001(π/2) < 8π.
For any point x ∈ Q 2 , let C(x) denote a shortest cycle in G such that x is contained in the open region bounded by the cycle. If the shortest cycle is not unique, we pick one which encloses the smallest area. It follows from Claim 4 below that this defines the shortest cycle C(x) uniquely, but this fact is not essential for the proof. Obviously, C(x) is a simple cycle (i.e., without self-intersections). Let R(x) denote the open region enclosed by C(x).

Claim 2
For every x ∈ Q 2 we have: (ii) Between two points p, q on C(x), there is always a shortest path on C(x) itself. Proof. (i) Since every subpath of a shortest path is a shortest path, it suffices to consider a path ξ(p, q) between two points p, q on C(x) whose interior is completely contained in R(x), see Figure 8a. This path could replace one of the two arcs of C(x) between p and q and yield a better cycle enclosing x, contradicting the definition of C(x).
(ii) We have already excluded shortest paths which intersect R(x). We now exclude a path ξ(p, q) between two points p, q on C(x) which runs outside C(x) and is strictly shorter than each of the two arcs of C(x) between p and q, see Figure 8b. If such a path existed, again, we could replace one of the arcs from C connecting p and q by ξ(p, q) and receive a shorter cycle encircling x, a contradiction.
As an immediate consequence of statement (ii), we get: Claim 3 The dilation of every cycle C(x) is at most the dilation δ(G) of the whole graph G.
This allows us to apply Lemma 6 to the cycles C(x). However, to obtain a packing, we still have to select a subset of cycles with disjoint regions. To this end we prove the following claim.
Claim 4 For arbitrary points x, y ∈ Q 2 , the cycles C(x) and C(y) are non-crossing, i.e., Proof. We argue by contradiction, see Figure 8c. Assume that the regions R 1 and R 2 of the shortest cycles C 1 := C(x) and C 2 := C(y) overlap, but none is fully contained inside the other. This implies that their union R 1 ∪ R 2 is a bounded open connected set. Its boundary ∂(R 1 ∪ R 2 ) contains a simple cycle C enclosing R 1 ∪ R 2 .
By the assumptions we know that there is a part C in 1 of C 1 which connects two points p, q ∈ C 2 and is, apart from its endpoints, completely contained in R 2 . Let C out 1 denote the other path on C 1 connecting p and q. By Claim 2(i), at least one of the paths C in 1 or C out 1 must be a shortest path. By Claim 2(ii), C in 1 cannot be a shortest path, since it intersects R 2 . Hence, only C out 1 is a shortest path, implying |C out 1 | < |C 1 | /2. Analogously, we can split C 2 into two paths C in 2 and C out 2 such that C in 2 is contained in R 1 , apart from its endpoints, and |C out 2 | < |C 2 | /2. The boundary cycle C consists of parts of C 1 and parts of C 2 . It cannot contain any part of C in 1 or C in 2 because it intersects neither with R 1 nor with R 2 . Hence |C| ≤ |C out 1 |+|C out 2 | < (|C 1 | + |C 2 |)/2 ≤ max{|C 1 | , |C 2 |}. Since C encloses x ∈ R 1 and y ∈ R 2 , this contradicts the choice of C 1 = C(x) or C 2 = C(y).
Let C be the set of shortest cycles C = { C(x) | x ∈ Q 2 }, and let M ⊂ C be the set of maximal shortest cycles with respect to inclusion of their regions. Claim 4 implies that these cycles have disjoint interiors and that they cover Q 2 . Claim 1 proves that their in-radius is bounded by r ≤ 4. By Claim 3, the dilation of every cycle C ∈ M satisfies δ(C) ≤ δ(G) ≤ ∆(Λ). Like described in the beginning of this proof we get a contradiction to Theorem 1. This completes the proof of the new lower bound (Theorem 2).

Closed Curves of Constant Halving Distance
Closed curves of constant halving distance turn up naturally if one wants to construct graphs of low dilation. Lemma 1 shows that the dilation of a convex curve of constant halving distance is attained by all its halving pairs. Hence, it is difficult to improve (decrease) the dilation of such cycles, because local changes decrease h or increase |C|. This is the motivation for using the curve of constant halving distance C F of Figure 9b to construct the grid of low dilation in Figure 2. Although the non-convex parts increase the length and thereby the dilation of the small flowers C F , they are useful in decreasing the dilation of the big faces of the graph.
The proof of Lemma 6 shows that only curves with constant midpoint m(t) and constant halving distance can attain the global dilation minimum of π/2. Furthermore, it shows that only circles satisfy both conditions; see also [9, Corollary 23], [1, Corollary 3.3], [16], [13]. What happens if only one of the conditions is satisfied? Clearly, m(t) is constant if and only if C is centrally symmetric. On the other hand, the class of closed curves of constant halving distance is not as easy to describe. One could guess -incorrectly -that it consists only Figure 9: The "Rounded Triangle" C △ and the "Flower" C F are curves of constant halving distance.
of circles. The "Rounded Triangle" C △ shown in Figure 9a is a convex counterexample, and could be seen as an analog of the Reuleaux triangle, the best-known representative of curves of constant width [4]. It seems to be a somehow prominent example, because two groups of the authors of this paper discovered it independently, before finding it in a paper of H. Auerbach [3, p. 141] from 1938.
We construct C △ by starting with a pair of points p := (0, 0.5) andp := (0, −0.5). Next, we move p to the right along a horizontal line. Simultaneously,p moves to the left such that the distance |pp| = 1 is preserved and both points move with equal speed. It can be shown that these conditions lead to a differential equation whose solution defines the path ofp uniquely. We move p andp like this until the connecting line segment pp forms an angle of 30 • with the y-axis. Next, we swap the roles of p andp. Now,p moves along a line with the direction of its last movement, and p moves with equal speed on the unique curve which guarantees |pp| = 1, until pp has rotated with another 60 • . Again, we swap the roles of p andp for the next 60 • and so forth. In this way we end up with six pieces of equal length (three straight line segments and three curved pieces) to build the Rounded Triangle C △ depicted in Figure 9a. Note that the rounded pieces are not parts of circles.
The details of the differential equation and its solution are given in Appendix C. Here, we mention only that the perimeter of C △ equals 3 ln 3. By Lemma 1 this results in The midpoint curve of C △ is built from six congruent pieces that are arcs of a tractrix, as we will discuss in the end of this section. First, we give a necessary and sufficient condition for curves of constant halving distance (not necessarily convex).
Theorem 3 Let C be a planar closed curve, and let c : [0, |C|) → C be an arc-length parameterization. Then, the following two statements are equivalent: 1. If c is differentiable in t and in t + |C|/2,ṁ(t) = 0, andċ * (t) = 0, then the halving chord c(t)c(t + |C|/2) is tangent to the midpoint curve at m(t). And if the midpoint stays at m ∈ Ê 2 on a whole interval (t 1 , t 2 ), the halving pairs are located on the circle with radius h(C)/2 and center point m.
2. The closed curve C is a cycle of constant halving distance.
Proof. "2. ⇒ 1." Let C have constant halving distance. If c is differentiable in t and t + |C|/2, c * and m are differentiable in t. And due to |c * | ≡ h(C)/2 it follows thatċ * (t) must be orthogonal to c * (t) which can be shown by On the other hand, we have already seen in (5) of Section 3 thatṁ(t) andċ * (t) are orthogonal. Hence,ṁ(t) = 0 =ċ * (t) impliesṁ(t) c * (t) and the first condition of 1. is proven. The second condition follows trivially from c(t) = m(t) + c * (t).
The range [0, |C|/2) can be divided into countably many disjoint intervals [t i , t i+1 ) where m and c * are differentiable on the open interval (t i , t i+1 ), and one of the three conditionṡ m(t) = 0,ċ * (t) = 0 orṁ(t) = 0 =ċ * (t) holds for the whole interval (t i , t i+1 ). We have shown that |c * | must be constant on all these open intervals. Thus, due to c * being continuous on [0, |C|/2), |c * | must be globally constant.
The theorem shows that curves of constant halving distance can consist of three types of parts; parts where the halving chords lie tangentially to the midpoint curve, circular arcs of radius h(C)/2, and parts whereċ * (t) = 0 and the halving pairs are only moved by the translation due to m, i.e., for every τ 1 and τ 2 within such a part we have c(τ 2 ) − c(τ 1 ) = c(τ 2 + |C|/2) − c(τ 1 + |C|/2) = m(τ 2 ) − m(τ 1 ). For convex cycles of constant halving pair distance, the translation parts cannot occur: Lemma 7 Let C be a closed convex curve of constant halving distance. Then there exists no non-empty interval (t 1 , t 2 ) ⊂ [0, |C|) such that c * is constant on (t 1 , t 2 ).
Proof. Assume that c * is constant on (t 1 , t 2 ) and choose s 1 , s 2 with t 1 < s 1 < s 2 < t 2 and s 2 < s 1 + |C|/2. If the four points p 1 = c(s 1 ), p 2 = c(s 2 ), p 3 = c(s 2 + |C|/2), p 4 = c(s 1 + |C|/2) do not lie on a line, they form a parallelogram in which p 1 p 4 and p 2 p 3 are parallel sides. However, these points appear on C in the cyclic order p 1 p 2 p 4 p 3 , which is different from their convex hull order p 1 p 2 p 3 p 4 (or its reverse), a contradiction. The case when the four points lie on a line ℓ can be dismissed easily (convexity of C implies that the whole curve C would have to lie on ℓ, but then C could not be a curve of constant halving distance). With the convexity requirement, we have proved that the halving chord is always tangent to the midpoint curve in all points where the midpoint curve has a tangent: the midpoint curve is the envelope of the halving segments. This is the viewpoint from which Zindler started his investigations in 1921: he was interested in envelopes of all sorts of halving chords (halving the perimeter, the area, etc., and not necessarily of constant length) and other classes of chords with special properties. For curves of constant halving distance, he observed the following interesting fact (without stating it explicitly as a theorem): Theorem 4 (Zindler [22,Section 7]) For a convex closed curve in the plane, the following statements are equivalent.
1. All halving chords have the same length.
2. All chords halving the area have the same length.

Halving chords and area-halving chords coincide.
Following Auerbach [3], these curves are consequently called Zindler curves. (The theorem holds also for non-convex curves as long as all halving chords go through the interior of C, and it remains even true for chords that divide the area or perimeter in some arbitrary constant ratio.) Auerbach [3] noted than these curves are related to a problem of S. Ulam about floating bodies. Ulam's original problem [18,Problem 19,, [5,Section A6,, [20, pp. 153-154], which is still unsolved in its generality, asks if there is a homogeneous body different from a spherical ball that can float in equilibrium in any orientation. A twodimensional version can be formulated as follows: consider a homogeneous cylindrical log of density 1 2 whose cross-section is a convex curve C, floating in water (which has density 1). This log will float in equilibrium with respect to rolling in every horizontal position if and only if C is a Zindler curve.
Moreover, Auerbach relates these curves to curves of constant width [4, § 7]: Theorem 5 (Auerbach [3]) If a square P QRS moves rigidly in the plane such the diagonal P R traces all halving chords of a Zindler curve C the endpoints of the other diagonal QS trace out a curve D of constant width, enclosing the same area as C.
Conversely, one can start from any curve of constant width. Taking point pairs Q and S with parallel tangents as diagonals of squares P QRS, the other diagonal P R will generate a curve of constant halving distance, not necessarily convex. Theorem 5 remains true for a rhombus P QRS as long as QS is it not too short, relatively to P R. (Of course, the area of D will then be different.)  Now we show that the midpoint curve of the Rounded Triangle C △ is built from six tractrix pieces. The tractrix is illustrated in Figure 11. A watch is placed on a table, say at the origin (0, 0) and the end of its watchchain of length 1 is pulled along the horizontal edge of the table starting at (0, 1), either to the left or to the right. As the watch is towed in the direction of the chain, the chain is always tangent to the path of the watch, the tractrix.
From the definition it is clear that the midpoint curve of the cycle C △ consists of such tractrix pieces, scaled by 1/2, because by definition and Theorem 3 its halving chords are always tangent to the midpoint curve, always one of the points of these pairs is moving on a straight line, and its distance to the midpoint curve stays 1/2. A parameterization not depending on the midpoint curve is analyzed in Appendix C.
As mentioned in the introduction, Zindler [22,Section 7.b] discovered some convex curves of constant halving distance already in 1921. He restricted his analysis to curves whose midpoint curves have three cusps like the one of the rounded triangle. His example uses as the midpoint curve the path of a point on a circle of radius 1 rolling inside of a bigger circle of radius 3 (a hypocycloid). To guarantee convexity, one then needs h ≥ 48.

Relating Halving Distance to other Geometric Quantities
One important topic in convex geometry is the relation between different geometric quantities of convex bodies like area A and diameter D. Scott and Awyong [19] give a short survey of basic inequalities in Ê 2 . For example, it is known that 4A ≤ πD 2 , and equality is attained only by circles, the so-called extremal set of this inequality.
In this context the minimum and maximum halving distance h and H give rise to some new interesting questions, namely the relation to other basic quantities like the width w.
As the inequality h ≤ w is immediate from definition, the known upper bounds on w hold for h as well. However, although the original inequalities relating w to perimeter, diameter, area, inradius and circumradius are tight (see [19]), not all of them are also tight for h. One counterexample (A ≥ w 2 / √ 3 ≥ h 2 / √ 3) will be discussed in the following subsection.

Minimum Halving Distance and Area
Here, we consider the relation of the minimum halving distance h and the area A. Clearly, the area can get arbitrarily big while h stays constant. For instance this is the case for a rectangle of smaller side length h where the bigger side length tends to infinity.
How small the area A can get for closed convex curves of minimum halving distance h? A first answer A ≥ h 2 / √ 3 is easy to prove, because it is known [21, ex. 6.4, p.221] that A ≥ w 2 / √ 3, and we combine this with w ≥ h. Still, 1/ √ 3 ≈ 0.577 is not the best possible lower bound to A/h 2 , since the equilateral triangle is the only closed curve attaining A = w 2 / √ 3 and its width w = √ 3/2 ≈ 0.866 (for side length 1) is strictly bigger than its minimum halving distance h = 3/4 = 0.75. We do not know the smallest possible value of A/h 2 .
We can also consider chords bisecting the area of planar convex sets instead of halving their perimeter, see [5, Section A26, p. 37] about "dividing up a piece of land by a short fence". Let h area be the minimum area-halving distance. Santaló asked 5 if A ≥ (π/4)h 2 area . Equality is attained by a circle. Now going back to perimeter halving distance, does the circle attain smallest area for a given h? Already the equilateral triangle gives a counterexample,   Figure 14: The midpoint curve of a rounded pentagon, constructed analogously to C △ of Figure 9, has 5 cusps. It contains regions with winding number 2 and regions with winding number 1.
smaller ratio A/h 2 than the circle. In fact, the circle maximizes A/h 2 among the curves of constant halving distance. The following formula was proved by Zindler [22,Theorem 24] for the special case of midpoint curves with three cusps. Here, we give a proof for the general case.
Lemma 8 If C is a convex cycle of constant halving distance h, its area satisfies A = (π/4)h 2 −2A(M ) where A(M ) denotes the area bounded by the midpoint curve M . In A(M ), the area of any region encircled several times by M is counted with the multiplicity of the corresponding winding number, see Figure 14 for an example. In particular, A ≤ (π/4)h 2 .
Proof. It suffices to analyze the case h = 2. And we assume that c is oriented counterclockwise. Then, we can consider the following parameterizations of C * and M in terms of the angle α of the current halving chord.
Such parameterizations exist for some function v : [0, 2π) → Ê because of Theorem 3 and Lemma 7. Periodicity requires m(α) = m(α + π) and thereby v(α + π) = −v(α). We say that v is antiperiodic in π. If x(α) denotes the x-coordinate of c(α) = c * (α) + m(α) and y(α) is the y-coordinate, we get The two integrals with marked terms disappear in the above equations because their integrands are antiperiodic in π. For the area of M we get analogously The negative sign here comes from the fact that M is traversed in the opposite orientation from C.
We have shown that the circle is the convex cycle of constant halving distance attaining maximum area. But which convex cycle of constant halving distance attains minimum area? We conjecture (in accordance with Auerbach [3, p. 138]) that the answer is the Rounded Triangle C △ . Lemma 8 helps us to calculate its area A(C △ ). The tractrix construction of the midpoint curve M makes it possible to get a closed form for A(M ). The value of the resulting expression for the area of C △ is This value (as well as the length of C △ ) has also been obtained by Auerbach [3], with a different method. Auerbach also proposed C △ as a candidate for a Zindler curve of maximum length.
Zindler's curve [22,Section 7.b], which we described in the end of Section 6, has area ((π/4)− (1/24) 2 π)h 2 ≈ 0.780h 2 . Both constant factors are smaller than π/4 ≈ 0.7854 . . ., thus providing a negative answer to the above-mentioned question of Santaló whether A ≥ (π/4)h 2 area . It would be interesting to know whether C △ has the smallest area among all convex curves with a given minimum area-halving distance h area .
Auerbach [3] constructed another, non-convex, curve of constant halving width, based on the same tractrix construction as the rounded triangle C △ , but consisting of only two straight edges and two smooth arcs, forming the shape of a heart. Approximate renditions of both curves can be found in several problem collections [18, Fig. 19.1, p. 91], [5,Fig. A9,p. 20], [20,Figs. 179 and 180, and other popular books, but they appear to use circular arcs instead of the correct boundary curves, given by the parametrization (19) in Appendix C.

Minimum Halving Distance and Width
In order to achieve a lower bound to h in terms of w, we examine the relation of both quantities to the area A and the diameter D. The following inequality was first proved by Kubota [14] in 1923 and is listed in [19].
We will combine this known inequality with the following new result.
Theorem 7 If C is a convex curve, then A ≤ Dh.
Proof. Without loss of generality we assume that a halving chord pp of minimum length h lies on the y-axis, p on top andp at the bottom, see Figure 15. Let C − be the part of C with negative x-coordinate and let C + := C \ C − be the remaining part. We have |C − | = |C + | = |C|/2 because pp is a halving chord. In Figure 15, obviously |C − | = |C + | does not hold, but this is only to illustrate our proof by contradiction. Let −x 1 and x 2 denote the minimum and maximum x-coordinate of C. Note that x 1 has a positive value. We assume that x 2 > x 1 . Otherwise we could reflect C at the y-axis. Let y(x) be the length of the vertical line segment of x-coordinate x inside C, for every x ∈ [−x 1 , x 2 ]. These definitions result in x 1 + x 2 ≤ D and A = x2 −x1 y(x) dx. Furthermore, if we take the convex hull of the vertical segment with x-coordinate x and length y(x) and the vertical segment with x-coordinate −x and length y(−x), then its intersection with the y-axis has length (y(−x) + y(x))/2. By convexity it must be contained in the line segment pp of length h. This implies ∀x ∈ [0, x 1 ] : y(−x) + y(x) ≤ 2h .
As a next step, we want to show that We assume that y(x) > h. Let ab be the vertical segment of x-coordinate x inside C, a on top and b at the bottom. Then, we consider the lines ℓ 1 through p and a and ℓ 2 through Finally, we achieve the desired inequality relating h and w.
Theorem 8 If C is a convex curve, then h ≥ w/2. This bound is tight.
Theorem 8 can be also proved directly by using arguments analogous to the proof of Theorem 7. But we think that Theorem 7 is of independent interest.
of Ebbers-Baumann et al. [9,Theorem 22]. The new upper bound is stated in the following theorem and plotted in Figure 16a.
Theorem 9 If C is a convex curve, then  (14).
Proof. Kubota [14] (see also [19]) showed that Combining this with Theorem 8 and Lemma 1 yields The isoperimetric inequality |C| ≤ Dπ and the inequality |C| ≤ 2D + 2w lead to the slightly bigger but simpler dilation bounds δ(C) ≤ π D w and δ(C) ≤ 2 D w + 1 , see Figure 16a. But even the dilation bound of Theorem 9 is not tight because (14) becomes an equality only for curves which result from the intersection of a circular disk of diameter D with a parallel strip of width w, see Figure 16b. For these curves we have h = w due to their central symmetry, but equality in our upper bound can only be attained for 2h = w.

Lower Bounds on the Geometric Dilation of Polygons
In this subsection we apply the lower bound (13) of Ebbers-Baumann et al. [9] to deduce lower bounds on the dilation of polygons with n sides (in special cases we proceed directly). We start with the case of a triangle (and skip the easy proof):
Equality is attained by equilateral triangles. Note that plugging the inequality D/w ≥ 2/ √ 3 into (13) would only give δ(C) ≥ π/3+1/ √ 3 ≈ 1.624. We continue with the case of centrally symmetric convex polygons, for which we obtain a tight bound.
Theorem 10 If C is a centrally symmetric convex n-gon (thus n is even), then This bound is tight.
Proof. We adapt the proof of Theorem 22 in [9], which proves inequality (13) for closed curves. Since C is centrally symmetric, it must contain a circle of radius r = h/2. It can easily be shown (using the convexity of the tangent function) that the shortest n-gon containing such a circle is a regular n-gon. Its length equals 2rn tan π/n which further implies that The bound is tight for a regular n-gon.
In the last part of this section we address the case of arbitrary (not necessarily convex) polygons. Let C be a polygon with n vertices, and let C ′ = conv(C). Clearly C ′ has at most n vertices. By Lemma 9 in [9], δ(C) ≥ δ(C ′ ). Further on, consider the convex curve obtained by central symmetrization from C ′ (see [21,9]). It is easy to check that C ′′ is a convex polygon, whose number of vertices n ′′ is even and at most twice that of C ′ , therefore at most 2n. Because δ(C ′′ ) ≤ δ(C ′ ) by Lemma 16 in [9], we get Theorem 10, n ′′ ≤2n ≥ n tan π 2n and obtain a lower bound on the geometric dilation of any polygon with n sides.

Corollary 2
The geometric dilation of any polygon C with n sides satisfies This inequality does not seem to be tight, even for odd n. The dilation of a regular polygon C with an odd number n of vertices can be calculated by using the fact that the curve C * obtained by the halving-pair transformation is a regular 2n-gon whose dilation equals δ(C * ) = n tan(π/2n). Because the derivative (unit-)vectorsċ(t) andċ(t + |C|/2) of an arc-length parameterization of C always enclose an angle (n − 1)π/n, we get Because of h(C * ) = h(C) and Lemma 1 we have δ(C)/δ(C * ) = |C|/|C * |, which results in δ(C) = 1 cos π 2n δ(C * ) = 1 cos π 2n n tan π 2n .

Conclusion and Open Questions
Our main result Theorem 2 looks like a very minor improvement over the easier bound ∆ ≥ π/2, but it settles the question whether ∆ > π/2 and has required the introduction of new techniques. Our approximations are not very far from optimal, and we believe that new ideas are required to improve the lower bound to, say, π/2 + 0.01. An improvement of the constant Λ = 1.00001 in the disk packing result of [15] (Theorem 1) would of course immediately imply a better bound for the dilation. It should be emphasized here that Theorem 1 holds for both finite and infinite packings. As we use it only for finite packings, it would be interesting to know if a substantially better result could be obtained for this presumably easier case.
We do not know whether the link between disk packing and dilation that we have established works in the opposite direction as well: Can one construct a graph of small dilation from a "good" circle packing (whose enlargement by a "small" factor covers a large area)? If this were true (in some meaningful sense which would have to be made precise) it would mean that a substantial improvement of the lower bound on dilation cannot be obtained without proving, at the same time, a strengthening of Theorem 1 with a larger constant than 1.00001. Overall, the gap between the lower bound (1 + 10 −11 )π/2 ≈ 1.571 and the upper bound 1.678 remains a challenging problem.
As mentioned in Section 7.1, we conjecture that the Rounded Triangle C △ of Figure 9a is the convex curve of constant halving distance minimizing the area.
Finally, it would be nice to find a tight lower bound on the geometric dilation of arbitrary (not only centrally-symmetric) convex polygons.

C Parameterization of the Rounded Triangle
In this section we solve a differential equation to give a parameterization c(t) = (x(t), y(t)) of a part of C △ . It is the first half rounded piece. As the curve C △ contains three curved pieces, it consists of six halves like the one described in the following. Together with the straight line segments of the same length they build the whole Rounded Triangle. The piece examined here starts at c(0) := (0, −0.5) and it is determined by the two conditions (x(t) − t) 2 + (y(t) − 0.5) 2 ≡ 1 and x ′ (t) 2 + y ′ (t) 2 ≡ 1 .
Solving the first one for y and taking the derivative with respect to t, and solving the second one for dy/dt yields By squaring we get the quadratic equation As the second possible solution x ′ (t) ≡ 1 does not make any sense in this context, we get x ′ (t) = 2(x(t) − t) 2 − 1 .