Fat object (geometry)

Many algorithms in computational geometry can perform much better if their input consists of only fat objects; see the applications section below.

The above definition can be termed two-cubes fatness since it is based on the ratio between the side-lengths of two cubes.

An alternative definition, that can be termed enclosing-ball fatness (also called "thickness"[3]) 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.

Similarly it is possible to define the enclosed-ball fatness based on the following slimness factor: The enclosing-ball/cube-slimness might be very different from the enclosed-ball/cube-slimness.

Thus the enclosing-cube-slimness can grow arbitrarily while the enclosed-cube-slimness remains constant (=√2).

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:

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 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).

Here is a proof sketch for fatness based on enclosing balls.

But every such enclosing ball b is in the set B considered by the definition of local-enclosing-ball slimness.

For a convex body, the opposite is also true: local-fatness implies global-fatness.

Proof sketch: standing at the point P, we can look at different angles θ and measure the distance to the boundary of o.

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

The definition of local-enclosing-ball slimness considers all balls that are centered in a point in o and intersect the boundary of o.

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

The following table shows the slimness factor of various shapes based on the different definitions.

The three ball-based slimness factors can be calculated using well-known trigonometric identities.

The largest circle contained in a triangle is called its incircle.

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

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]

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:

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:

at its wide side; similarly, the height of the segment ranges between

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

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

If an object o has diameter 2a, then every ball enclosing o must have radius at least a and volume at least

Hence, by definition of enclosing-ball-fatness, the volume of an R-fat object with diameter 2a must be at least

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 42 = 16 (this is not a tight bound since in this case it is easy to prove an upper bound of 5).