fat object (geometry)

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; see the applications section 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 is:

:$\frac$

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. 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") is based on the following slimness factor:

:$\left(\frac\right)^$

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\right)^$

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 thi
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$

A ''d''-dimensional cube with side-length 2''a'' has volume (2''a'')^''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 ⋅ $^\cdot / 2$.

For even dimensions (''d''=2''k''), the factor simplifies to: $\sqrt /$. 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 ⋅ $^\cdot / 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 2''a''. Hence for every ''d''-dimensional object:
::enclosing-cube-slimness ≤ enclosing-ball-slimness ⋅ $2 / ^$

For even dimensions (''d''=2''k''), the factor simplifies to: $2 / ^ /$. 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 / ^$
::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:

:$\frac\cdot \sup_\left(\frac\right)^$

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 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 \geq \frac$

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$

Similarly we can calculate the right-hand side of the inequality by integrating the following function:
::$F(\theta) = \min$

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 \ (b)\leq C_d\cdot \text \ (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 \ 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):

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 + \cot \frac + \cot \frac)$

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$

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.

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$

It is also known that:

:$\Delta = \frac = \frac$

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 = \sqrt$

Note that in a right triangle, $\sin=\sin=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:

:$\frac = \frac = \frac$

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

:$\frac = R \sin$

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

:$\frac = \frac = \frac$

Note that in a right triangle, $\sin=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 = \frac$

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 \approx \frac=\frac$

The following graphs show the 2-balls slimness factor of a triangle:
* Slimness of a general triangl
when one angle (''a'') is a constant parameter while the other angle (''x'') changes

* Slimness of an isosceles triangl
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 approximation when ''θ'' is small) is:
:$\frac=\frac=\frac \approx \frac = \frac$

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=\frac=\frac \approx \frac = \frac$

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$ at the narrow side of the ellipse and $2b\sin\frac$ at its wide side; similarly, the height of the segment ranges between $b\left(1-\cos\frac\right)$ at the narrow side and $a\left(1-\cos\frac\right)$ at its wide side. So the two-balls slimness ranges between:
:$\frac \approx \frac$

and:
:$\frac \approx \frac$

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

:$\frac$ $\left(\frac\cos^2(\Theta+\frac) + \frac\sin^2(\Theta+\frac)\right)$

Fatness of a convex polygon

A convex polygon is called ''r''-separated if the angle between each pair of edges (not necessarily adjacent) is at least ''r''.

Lemma: The enclosing-ball-slimness of an ''r''-separated convex polygon is at most $O(1/r)$.

A convex polygon is called ''k,r''-separated if:
# It does not have parallel edges, except maybe two horizontal and two vertical.
# Each non-axis-parallel edge makes an angle of at least ''r'' with any other edge, and with the x and y axes.
# If there are two horizontal edges, then diameter/height is at most ''k''.
# If there are two vertical edges, then diameter/width is at most ''k''.

Lemma: The enclosing-ball-slimness of a ''k,r''-separated convex polygon is at most $O(\max(k,1/r))$.. Conference version: improve the upper bound to $O(d)$.

Counting fat objects

If an object ''o'' has diameter 2''a'', 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 2''a'' 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 2''a'', contained in a ball of radius ''C⋅a'', is at most:
::$V_d\cdot (C a)^d / (V_d \cdot a^d / R^d) = (R C)^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:

: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 2''a''. Then the number of objects in the collection with diameter larger than 2''a'' that lie within distance ''2C⋅a'' from object ''o'' is at most:
::$(4 R \cdot (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 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.

Applications

Fat objects are used in various problems, for example:
* Motion planning - planning a path for a robot moving amidst obstacles becomes easier when the obstacles are fat objects.
* Fair cake-cutting - dividing a cake becomes more difficult when the pieces have to be fat objects. This requirement is common, for example, when the "cake" to be divided is a land-estate.
* More applications can be found in the references below.

References

{{reflist

Geometry
Computational geometry