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; 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:
where o and the cubes are d-dimensional. A 2-dimensional cube is a square, so the slimness factor of a square is 1. 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, 3-fat, etc. A disk is also 2-fat, 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 is based on the following slimness factor:
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:

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× rectangle. As b increases, the area of the enclosing cube increases, but the area of the enclosed cube remains constant and the total area of the shape also remains constant. Thus the enclosing-cube-slimness can grow arbitrarily while the enclosed-cube-slimness remains constant. See this 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 decreases, but the total areas of the snake and of the enclosing cube remain constant. Thus the enclosed-cube-slimness can grow arbitrarily while the enclosing-cube-slimness remains constant.
With both the lollipop and the snake, the two-cubes-slimness grows arbitrarily, since in general:
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.

Balls vs. cubes

The volume of a d-dimensional ball of radius r is:, where Vd is a dimension-dependent constant:
A d-dimensional cube with side-length 2a has volume d. It is enclosed in a d-dimensional ball with radius a√d whose volume is Vdd. Hence for every d-dimensional object:
For even dimensions, the factor simplifies to:. In particular, for two-dimensional shapes V2=π and the factor is: √≈1.25, so:
From similar considerations:
A d-dimensional ball with radius a is enclosed in a d-dimensional cube with side-length 2a. Hence for every d-dimensional object:
For even dimensions, the factor simplifies to:. In particular, for two-dimensional shapes the factor is: 2/√π≈1.13, so:
From similar considerations:
Multiplying the above relations gives the following simple relations:
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× rectangle. As b increases, the area of the enclosing cube and the area of the enclosed cube remain constant, while the total area of the shape changes only slightly. 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. The local-enclosing-ball-slimness factor is defined as:
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× 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:
Hence:
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.:
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 over all angles:
Similarly we can calculate the right-hand side of the inequality by integrating the following function:
By checking all 3 possible cases, it is possible to show that always. 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. For every such ball b:
where 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:. Combining all inequalities gives that for every convex object:
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 :
Shapetwo-ballstwo-cubesenclosing-ballenclosing-cubeenclosed-ballenclosed-cubelocal-enclosing-balllocal-enclosing-cube
square√21√≈1.251√ ≈ 1.131**
b×a rectangle with b>a√b/a0.5√π√2√√**
disk1√21√≈1.131√≈1.25**
ellipse with radii b>ab/a>b/a√>√√>√**
semi-ellipse with radii b>a, halved in parallel to b2b/a>2b/a√>√√>√**
semidisk2√5√2√≈1.6√2√≈1.4**
equilateral triangle1+2/√3≈2.15√≈1.35√≈1.52√√3/2+1/√√3≈1.42**
isosceles right-angled triangle1/≈2.42√2√2**
'lollipop' made of unit square and b×a stick, b>1>ab+1√^2/)√√

Fatness of a triangle

Slimness is invariant to scale, so the slimness factor of a triangle 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:
where Δ is the area of a triangle and r is the radius of the incircle. Hence, the enclosed-ball slimness of a triangle is:

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:
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:
It is also known that:
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, the enclosing-ball slimness factor is:
Note that in a right triangle,, 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:
For an obtuse triangle, c/2 should be used instead of R. By the Law of sines:
Hence the slimness factor of an obtuse triangle with obtuse angle C is:
Note that in a right triangle,, 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:
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:
The following graphs show the 2-balls slimness factor of a triangle:
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 is:
For a circular sector with central angle θ, the circumcircle diameter is the radius of the circle and the incircle diameter is the chord length, so the two-balls slimness is:
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 at the narrow side of the ellipse and at its wide side; similarly, the height of the segment ranges between at the narrow side and at its wide side. So the two-balls slimness ranges between:
and:
In general, when the secant starts at angle Θ the slimness factor can be approximated by:

Fatness of a convex polygon

A convex polygon is called r-separated if the angle between each pair of edges is at least r.
Lemma: The enclosing-ball-slimness of an r-separated convex polygon is at most.
A convex polygon is called k,r-separated if:
  1. It does not have parallel edges, except maybe two horizontal and two vertical.
  2. Each non-axis-parallel edge makes an angle of at least r with any other edge, and with the x and y axes.
  3. If there are two horizontal edges, then diameter/height is at most k.
  4. 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. improve the upper bound to.

Counting fat objects

If an object o has diameter 2a, then every ball enclosing o must have radius at least a and volume at least Vdad. Hence, by definition of enclosing-ball-fatness, the volume of an R-fat object with diameter 2a must be at least: Vdad/Rd. Hence:
For example : The number of non-overlapping disks with radius at least 1 contained in a circle of radius 3 is at most 32=9..
If we consider local-fatness instead of global-fatness, we can get a stronger lemma:
For example : the number of non-overlapping disks with radius larger than 1 that touch a given unit disk is at most 42=16.

Generalizations

The following generalization of fatness were studied by for 2-dimensional objects.
A triangle ∆ is a -triangle of a planar object o, if ∆ ⊆ o, each of the angles of ∆ is at least β, and the length of each of its edges is at least δ·diameter. 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: