Fat object

In geometry, a fat object is an object in two or more dimensions, whose lengths in the different dimensions are similar. For example, a square is fat because its length and width are identical. A 2-by-1 rectangle is thinner than a square, but it is fat relative to a 10-by-1 rectangle. Similarly, a circle is fatter than a 1-by-10 ellipse and an equilateral triangle is fatter than a very obtuse triangle.

Fat objects are especially important in computational geometry. Many algorithms in computational geometry can perform much better if their input consists of only fat objects. Some examples can be seen in the references below.

Global fatness

Given a constant R≥1, an object o is called R-fat if its "slimness factor" is at most R. The "slimness factor" has different definitions in different papers. A common definition^[1] is:

$\frac{\text{side of smallest cube enclosing} \ o}{\text{side of largest cube enclosed in} \ o}$

where o and the cubes are d-dimensional. A 2-dimensional cube is a square, so the slimness factor of a square is 1 (since its smallest enclosing square is the same as its largest enclosed disk). The slimness factor of a 10-by-1 rectangle is 10. The slimness factor of a circle is √2. Hence, by this definition, a square is 1-fat but a disk and a 10×1 rectangle are not 1-fat. A square is also 2-fat (since its slimness factor is less than 2), 3-fat, etc. A disk is also 2-fat (and also 3-fat etc.), but a 10×1 rectangle is not 2-fat. Every shape is ∞-fat, since by definition the slimness factor is always at most ∞.

The above definition can be termed two-cubes fatness since it is based on the ratio between the side-lengths of two cubes. Similarly, it is possible to define two-balls fatness, in which a d-dimensional ball is used instead.^[2] A 2-dimensional ball is a disk. According to this alternative definition, a disk is 1-fat but a square is not 1-fat, since its two-balls-slimness is √2.

An alternative definition, that can be termed enclosing-ball fatness (also called "thickness"^[3]) is based on the following slimness factor:

$\left(\frac{\text{volume of smallest ball enclosing} \ o}{\text{volume of} \ o}\right)^{1/d}$

The exponent 1/d makes this definition a ratio of two lengths, so that it is comparable to the two-balls-fatness.

Here, too, a cube can be used instead of a ball.

Similarly it is possible to define the enclosed-ball fatness based on the following slimness factor:

$\left(\frac{\text{volume of} \ o}{\text{volume of largest ball enclosed in} \ o}\right)^{1/d}$

Enclosing-fatness vs. enclosed-fatness

The enclosing-ball/cube-slimness might be very different from the enclosed-ball/cube-slimness.

For example, consider a lollipop with a candy in the shape of a 1×1 square and a stick in the shape of a b×(1/b) rectangle (with b>1>(1/b)). As b increases, the area of the enclosing cube (≈b²) increases, but the area of the enclosed cube remains constant (=1) and the total area of the shape also remains constant (=2). Thus the enclosing-cube-slimness can grow arbitrarily while the enclosed-cube-slimness remains constant (=√2). See this GeoGebra page for a demonstration.

On the other hand, consider a rectilinear 'snake' with width 1/b and length b, that is entirely folded within a square of side length 1. As b increases, the area of the enclosed cube(≈1/b²) decreases, but the total areas of the snake and of the enclosing cube remain constant (=1). Thus the enclosed-cube-slimness can grow arbitrarily while the enclosing-cube-slimness remains constant (=1).

With both the lollipop and the snake, the two-cubes-slimness grows arbitrarily, since in general:

enclosing-ball-slimness ⋅ enclosed-ball-slimness = two-balls-slimness

enclosing-cube-slimness ⋅ enclosed-cube-slimness = two-cubes-slimness

Since all slimness factor are at least 1, it follows that if an object o is R-fat according to the two-balls/cubes definition, it is also R-fat according to the enclosing-ball/cube and enclosed-ball/cube definitions (but the opposite is not true, as exemplified above).

Balls vs. cubes

The volume of a d-dimensional ball of radius r is: $V_d\cdot r^d$, where V_d is a dimension-dependent constant:

$V_d = \frac{\pi^{d/2}}{\Gamma(\frac{d}{2} + 1)}$

A d-dimensional cube with side-length 2a has volume (2a)^d. It is enclosed in a d-dimensional ball with radius a√d whose volume is V_d(a√d)^d. Hence for every d-dimensional object:

enclosing-ball-slimness ≤ enclosing-cube-slimness ⋅ ${V_d}^{1/d}\cdot {\sqrt d} / 2$.

For even dimensions (d=2k), the factor simplifies to: $\sqrt{0.5 \pi k} / {{(k!)}^{1/2k}}$. In particular, for two-dimensional shapes V₂=π and the factor is: √(0.5 π)≈1.25, so:

enclosing-disk-slimness ≤ enclosing-square-slimness ⋅ 1.25

From similar considerations:

enclosed-cube-slimness ≤ enclosed-ball-slimness ⋅ ${V_d}^{1/d}\cdot {\sqrt d} / 2$

enclosed-square-slimness ≤ enclosed-disk-slimness ⋅ 1.25

A d-dimensional ball with radius a is enclosed in a d-dimensional cube with side-length 2a. Hence for every d-dimensional object:

enclosing-cube-slimness ≤ enclosing-ball-slimness ⋅ $2 / {V_d}^{1/d}$

For even dimensions (d=2k), the factor simplifies to: $2 / {(k!)}^{1/2k} / {\sqrt{\pi}}$. In particular, for two-dimensional shapes the factor is: 2/√π≈1.13, so:

enclosing-square-slimness ≤ enclosing-disk-slimness ⋅ 1.13

From similar considerations:

enclosed-ball-slimness ≤ enclosed-cube-slimness ⋅ $2 / {V_d}^{1/d}$

enclosed-disk-slimness ≤ enclosed-square-slimness ⋅ 1.13

Multiplying the above relations gives the following simple relations:

two-balls-slimness ≤ two-cubes-slimness ⋅ √d

two-cubes-slimness ≤ two-balls-slimness ⋅ √d

Thus, an R-fat object according to the either the two-balls or the two-cubes definition is at most R√d-fat according to the alternative definition.

Local fatness

The above definitions are all global in the sense that they don't care about small thin areas that are part of a large fat object.

For example, consider a lollipop with a candy in the shape of a 1×1 square and a stick in the shape of a 1×(1/b) rectangle (with b>1>(1/b)). As b increases, the area of the enclosing cube (=4) and the area of the enclosed cube (=1) remain constant, while the total area of the shape changes only slightly (=1+1/b). Thus all three slimness factors are bounded: enclosing-cube-slimness≤2, enclosed-cube-slimness≤2, two-cube-slimness=2. Thus by all definitions the lollipop is 2-fat. However, the stick-part of the lollipop obviously becomes thinner and thinner.

In some applications, such thin parts are unacceptable, so local fatness, based on a local slimness factor, may be more appropriate. For every global slimness factor, it is possible to define a local version. For example, for the enclosing-ball-slimness, it is possible to define the local-enclosing-ball slimness factor of an object o by considering the set B of all balls whose center is inside o and whose boundary intersects the boundary of o (i.e. not entirely containing o). The local-enclosing-ball-slimness factor is defined as:^[3][4]

$\frac{1}{2}\cdot \sup_{b \in B}\left(\frac{\text{volume of} \ B}{\text{volume of} \ B\cap o}\right)^{1/d}$

The 1/2 is a normalization factor that makes the local-enclosing-ball-slimness of a ball equal to 1. The local-enclosing-ball-slimness of the lollipop-shape described above is dominated by the 1×(1/b) stick, and it goes to ∞ as b grows. Thus by the local definition the above lollipop is not 2-fat.

Global vs. local definitions

Local-fatness implies global-fatness. Here is a proof sketch for fatness based on enclosing balls. By definition, the volume of the smallest enclosing ball is ≤ the volume of any other enclosing ball. In particular, it is ≤ the volume of any enclosing ball whose center is inside o and whose boundary touches the boundary of o. But every such enclosing ball is in the set B considered by the definition of local-enclosing-ball slimness. Hence:

enclosing-ball-slimness^d =

= volume(smallest-enclosing-ball)/volume(o)

≤ volume(enclosing-ball-b-in-B)/volume(o)

= volume(enclosing-ball-b-in-B)/volume(b ∩ o)

≤ (2 local-enclosing-ball-slimness)^d

Hence:

enclosing-ball-slimness ≤ 2⋅local-enclosing-ball-slimness

For a convex body, the opposite is also true: local-fatness implies global-fatness. The proof^[3] is based on the following lemma. Let o be a convex object. Let P be a point in o. Let b and B be two balls centered at P such that b is smaller than B. Then o intersects a larger portion of b than of B, i.e.:

$\frac{\text{volume} \ (b \cap o)}{\text{volume} \ (b)} \geq \frac{\text{volume} \ (B \cap o)}{\text{volume} \ (B)}$

Proof sketch: standing at the point P, we can look at different angles θ and measure the distance to the boundary of o. Because o is convex, this distance is a function, say r(θ). We can calculate the left-hand side of the inequality by integrating the following function (multiplied by some determinant function) over all angles:

$f(\theta) = \min{(\frac{r(\theta)}{\text{radius} \ (b)},1)}$

Similarly we can calculate the right-hand side of the inequality by integrating the following function:

$F(\theta) = \min{(\frac{r(\theta)}{\text{radius} \ (B)},1)}$

By checking all 3 possible cases, it is possible to show that always $f(\theta)\geq F(\theta)$. Thus the integral of f is at least the integral of F, and the lemma follows.

The definition of local-enclosing-ball slimness considers all balls that are centered in a point in o and intersect the boundary of o. However, when o is convex, the above lemma allows us to consider, for each point in o, only balls that are maximal in size, i.e., only balls that entirely contain o (and whose boundary intersects the boundary of o). For every such ball b:

$\text{volume} \ (b)\leq C_d\cdot \text{diameter} \ (o)^d$

where $C_d$ is some dimension-dependent constant.

The diameter of o is at most the diameter of the smallest ball enclosing o, and the volume of that ball is: $C_d\cdot(\text{diameter(smallest ball enclosing} \ o)/2)^d$. Combining all inequalities gives that for every convex object:

local-enclosing-ball-slimness ≤ enclosing-ball-slimness

For non-convex objects, this inequality of course doesn't hold, as exemplified by the lollipop above.

Examples

The following table shows the slimness factor of various shapes based on the different definitions. The two columns of the local definitions are filled with "*" when the shape is convex (in this case, the value of the local slimness equals the value of the corresponding global slimness):

Shape	two-balls	two-cubes	enclosing-ball	enclosing-cube	enclosed-ball	enclosed-cube	local-enclosing-ball	local-enclosing-cube
square	√2	1	√(π/2)≈1.25	1	√(4/π) ≈ 1.13	1	*	*
b×a rectangle with b>a	√(1+b^2/a^2)	b/a	0.5√π(a/b+b/a)[3]	√(b/a)	2√(b/aπ)	√(b/a)	*	*
disk	1	√2	1	√(4/π)≈1.13	1	√(π/2)≈1.25	*	*
ellipse with radii b>a	b/a	>b/a	√(b/a)	>√(b/2πa)	√(b/a)	>√(πb/a)	*	*
semi-ellipse with radii b>a, halved in parallel to b	2b/a	>2b/a	√(2b/a)	>√(4b/πa)	√(2b/a)	>√(2πb/a)	*	*
semidisk	2	√5	√2	√(8/π)≈1.6	√2	√(5π/8)≈1.4	*	*
equilateral triangle		1+2/√3≈2.15	√(π/√3)≈1.35	√(4/√3)≈1.52		√√3/2+1/√√3≈1.42	*	*
isosceles right-angled triangle	1/(√2-1)≈2.4	2		√2		√2	*	*
'lollipop' made of unit square and b×a stick, b>1>a		b+1		√((b+1)^2/(ab+1))		√(ab+1)		√(b/a)

Fatness of a triangle

Slimness is invariant to scale, so the slimness factor of a triangle (as of any other polygon) can be presented as a function of its angles only. The three ball-based slimness factors can be calculated using well-known trigonometric identities.

Enclosed-ball slimness

The largest circle contained in a triangle is called its incircle. It is known that:

$\Delta = r^2\cdot(\cot \frac{\angle A}{2} + \cot \frac{\angle B}{2} + \cot \frac{\angle C}{2})$

where Δ is the area of a triangle and r is the radius of the incircle. Hence, the enclosed-ball slimness of a triangle is:

$\sqrt{ \frac{\cot \frac{\angle A}{2} + \cot \frac{\angle B}{2} + \cot \frac{\angle C}{2}}{\pi} }$

Enclosing-ball slimness

The smallest containing circle for an acute triangle is its circumcircle, while for an obtuse triangle it is the circle having the triangle's longest side as a diameter.^[5]

It is known that:

$\Delta = R^2 \cdot 2 \sin A \sin B \sin C$

where again Δ is the area of a triangle and R is the radius of the circumcircle. Hence, for an acute triangle, the enclosing-ball slimness factor is:

$\sqrt{\frac{\pi}{2 \sin A \sin B \sin C}}$

It is also known that:

$\Delta = \frac{c^{2}}{2(\cot \angle{A} + \cot \angle{B})} = \frac{c^{2} (\sin \angle{A})(\sin \angle{B})}{2\sin(\angle{A} + \angle{B})}$

where c is any side of the triangle and A,B are the adjacent angles. Hence, for an obtuse triangle with acute angles A and B (and longest side c), the enclosing-ball slimness factor is:

$\sqrt{\frac{\pi\cdot(\cot \angle{A} + \cot \angle{B})}{2}} = \sqrt{\frac{\pi\cdot\sin(\angle{A} + \angle{B})}{2 (\sin \angle{A}) (\sin \angle{B})}}$

Note that in a right triangle, $\sin{\angle{C}}=\sin{\angle{A}+\angle{B}}=1$, so the two expressions coincide.

Two-balls slimness

The inradius r and the circumradius R are connected via a couple of formulae which provide two alternative expressions for the two-balls slimness of an acute triangle:^[6]

$\frac{R}{r} = \frac{1}{4 \sin(\frac{\angle{A}}{2}) \sin(\frac{\angle{B}}{2}) \sin(\frac{\angle{C}} {2})} = \frac{1}{\cos \angle{A} + \cos \angle{B} + \cos \angle{C} - 1}$

For an obtuse triangle, c/2 should be used instead of R. By the Law of sines:

$\frac{c}{2} = R \sin{\angle{C}}$

Hence the slimness factor of an obtuse triangle with obtuse angle C is:

$\frac{c/2}{r} = \frac{\sin{\angle{C}}}{4 \sin(\frac{\angle{A}}{2}) \sin(\frac{\angle{B}}{2}) \sin(\frac{\angle{C}} {2})} = \frac{\sin{\angle{C}}}{\cos \angle{A} + \cos \angle{B} + \cos \angle{C} - 1}$

Note that in a right triangle, $\sin{\angle{C}}=1$, so the two expressions coincide.

The two expressions can be combined in the following way to get a single expression for the two-balls slimness of any triangle with smaller angles A and B:

$\frac{\sin{\max(\angle{A},\angle{B},\angle{C},\pi/2)}}{4 \sin(\frac{\angle{A}}{2}) \sin(\frac{\angle{B}}{2}) \sin(\frac{\pi-\angle{A}-\angle{B}} {2})} = \frac{\sin{\max(\angle{A},\angle{B},\angle{C},\pi/2)}}{\cos \angle{A} + \cos \angle{B} - \cos (\angle{A}+\angle{B}) - 1}$

To get a feeling of the rate of change in fatness, consider what this formula gives for an isosceles triangle with head angle θ when θ is small:

$\frac{\sin{\max(\theta,\pi/2)}}{4 \sin^2(\frac{\pi-\theta}{4}) \sin(\frac{\theta}{2})} \approx \frac{1}{4 {\sqrt{1/2}}^2 \theta/2}=\frac{1}{\theta}$

The following graphs show the 2-balls slimness factor of a triangle:

• Slimness of a general triangle when one angle (a) is a constant parameter while the other angle (x) changes.
• Slimness of an isosceles triangle as a function of its head angle (x).

Fatness of circles, ellipses and their parts

The ball-based slimness of a circle is of course 1 - the smallest possible value.

For a circular segment with central angle θ, the circumcircle diameter is the length of the chord and the incircle diameter is the height of the segment, so the two-balls slimness (and its approximaion when θ is small) is:

$\frac{\text{length of chord}}{\text{height of segment}}=\frac{2R\sin\frac{\theta}{2}}{R\left(1-\cos\frac{\theta}{2}\right)}=\frac{2\sin\frac{\theta}{2}}{\left(1-\cos\frac{\theta}{2}\right)} \approx \frac{\theta}{\theta^2/8} = \frac{8}{\theta}$

For a circular sector with central angle θ (when θ is small), the circumcircle diameter is the radius of the circle and the incircle diameter is the chord length, so the two-balls slimness is:

$\frac{\text{radius of circle}}{\text{length of chord}}=\frac{R}{2R\sin\frac{\theta}{2}}=\frac{1}{2\sin\frac{\theta}{2}} \approx \frac{1}{2 \theta / 2} = \frac{1}{\theta}$

For an ellipse, the slimness factors are different in different locations. For example, consider an ellipse with short axis a and long axis b. the length of a chord ranges between $2a\sin\frac{\theta}{2}$ at the narrow side of the ellipse and $2b\sin\frac{\theta}{2}$ at its wide side; similarly, the height of the segment ranges between $b\left(1-\cos\frac{\theta}{2}\right)$ at the narrow side and $a\left(1-\cos\frac{\theta}{2}\right)$ at its wide side. So the two-balls slimness ranges between:

$\frac{2a\sin\frac{\theta}{2}}{b\left(1-\cos\frac{\theta}{2}\right)} \approx \frac{8a}{b\theta}$

and:

$\frac{2b\sin\frac{\theta}{2}}{a\left(1-\cos\frac{\theta}{2}\right)} \approx \frac{8b}{a\theta}$

In general, when the secant starts at angle Θ the slimness factor can be approximated by:^[7]

$\frac{2\sin\frac{\theta}{2}}{\left(1-\cos\frac{\theta}{2}\right)}$ $\left(\frac{b}{a}\cos^2(\Theta+\frac{\theta}{2}) + \frac{a}{b}\sin^2(\Theta+\frac{\theta}{2})\right)$

Lemmas

If an object o has diameter 2a, then every ball enclosing o must have radius at least a and volume at least V_da^d. Hence, by definition of enclosing-ball-fatness, the volume of an R-fat object with diameter 2a must be at least: V_da^d/R^d. Hence:

Lemma 1: Let R≥1 and C≥0 be two constants. Consider a collection of non-overlapping d-dimensional objects that are all globally R-fat (i.e. with enclosing-ball-slimness ≤ R). The number of such objects of diameter at least 2a, contained in a ball of radius C⋅a, is at most: V_d(Ca)^d/(V_da^d/R^d) = (RC)^d.

For example (taking d=2, R=1 and C=3): The number of non-overlapping disks with radius at least 1 contained in a circle of radius 3 is at most 3²=9. (Actually, it is at most 7).

If we consider local-fatness instead of global-fatness, we can get a stronger lemma:^[3]

Lemma 2: Let R≥1 and C≥0 be two constants. Consider a collection of non-overlapping d-dimensional objects that are all locally R-fat (i.e. with local-enclosing-ball-slimness ≤ R). Let o be a single object in that collection with diameter 2a. Then the number of objects in the collection with diameter larger than 2a that lie within distance 2C⋅a from object o is at most (4R(C+1))^d.

For example (taking d=2, R=1 and C=0): the number of non-overlapping disks with radius larger than 1 that touch a given unit disk is at most 4²=16 (this is not a tight bound since in this case it is easy to prove an upper bound of 5).

Generalizations

The following generalization of fatness were studied by ^[2] for 2-dimensional objects.

A triangle ∆ is a (β, δ)-triangle of a planar object o (0<β≤π/3, 0<δ< 1), if ∆ ⊆ o, each of the angles of ∆ is at least β, and the length of each of its edges is at least δ·diameter(o). An object o in the plane is (β,δ)-covered if for each point P ∈ o there exists a (β, δ)-triangle ∆ of o that contains P.

For convex objects, the two definitions are equivalent, in the sense that if o is α-fat, for some constant α, then it is also (β,δ)-covered, for appropriate constants β and δ, and vice versa. However, for non-convex objects the definition of being fat is more general than the definition of being (β, δ)-covered.^[2]

References

1. Katz, M. J. (1997). "3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects". Computational Geometry 8 (6): 299. doi:10.1016/s0925-7721(96)00027-2., Agarwal, P. K.; Katz, M. J.; Sharir, M. (1995). "Computing depth orders for fat objects and related problems". Computational Geometry 5 (4): 187. doi:10.1016/0925-7721(95)00005-8.
2. Efrat, A.; Katz, M. J.; Nielsen, F.; Sharir, M. (2000). "Dynamic data structures for fat objects and their applications". Computational Geometry 15 (4): 215. doi:10.1016/s0925-7721(99)00059-0.
3. Van Der Stappen, A. F.; Halperin, D.; Overmars, M. H. (1993). "The complexity of the free space for a robot moving amidst fat obstacles". Computational Geometry 3 (6): 353. doi:10.1016/0925-7721(93)90007-s.
4. Berg, M.; Groot, M.; Overmars, M. (1994). "New results on binary space partitions in the plane (extended abstract)". Algorithm Theory — SWAT '94. Lecture Notes in Computer Science 824. p. 61. doi:10.1007/3-540-58218-5_6. ISBN 978-3-540-58218-2., Van Der Stappen, A. F.; Overmars, M. H. (1994). "Motion planning amidst fat obstacles (extended abstract)". Proceedings of the tenth annual symposium on Computational geometry - SCG '94. p. 31. doi:10.1145/177424.177453. ISBN 0897916484., Overmars, M. H. (1992). "Point location in fat subdivisions". Information Processing Letters 44 (5): 261. doi:10.1016/0020-0190(92)90211-d., Overmars, M. H.; Van Der Stappen, F. A. (1996). "Range Searching and Point Location among Fat Objects". Journal of Algorithms 21 (3): 629. doi:10.1006/jagm.1996.0063.
5. "How fat is a triangle?". Math.SE. Retrieved 28 September 2014.
6. Weisstein, Eric W. "Inradius". MathWorld. Retrieved 28 September 2014.
7. See graph at: https://www.desmos.com/calculator/fhfqju02sn