Fat object (geometry)

Uses your system voice; voice and rate in settings.

Snapshot

≈ 13 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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. For example, consider a lollipop with a candy in the shape of a square and a stick in the shape of a rectangle (with ). As increases, the area of the enclosing cube ( ) 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 and length , that is entirely folded within a square of side length 1. As increases, the area of the enclosed cube ( ) 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: \left({\text{enclosing-ball-} \atop \text{slimness}}\right) \times \left({\text{enclosed-ball-} \atop \text{slimness}}\right) = \left({\text{two-balls-} \atop \text{slimness}}\right) \left({\text{enclosing-cube-} \atop \text{slimness}}\right) \times \left({\text{enclosed-cube-} \atop \text{slimness}}\right) = \left({\text{two-cubes-} \atop \text{slimness}}\right) Since all slimness factor are at least 1, it follows that if an object is -fat according to the two-balls/cubes definition, it is also -fat according to the enclosing-ball/cube and enclosed-ball/cube definitions (but the opposite is not true, as exemplified above). V_d = \frac{\pi^{d/2}}{\Gamma \left(\frac{d}{2} + 1 \right)} A -dimensional cube with side-length has volume . It is enclosed in a -dimensional ball with radius a\sqrt d whose volume is V_d \left(a\sqrt d \right)^d. Hence for every -dimensional object: \left({\text{enclosing-ball-} \atop \text{slimness}}\right) \leq \left({\text{enclosing-cube-} \atop \text{slimness}}\right) \times \sqrt[d]{V_d} \times \frac{\sqrt d}{2} For even dimensions ( ), the factor simplifies to: \sqrt\tfrac{\pi k}{2} \left/ \sqrt[2k]{k!} \right. . In particular, for two-dimensional shapes and the factor is: \sqrt{\tfrac{\pi}{2}} \approx 1.25, so: \left({\text{enclosing-disk-} \atop \text{slimness}}\right) \leq \left({\text{enclosing-square-} \atop \text{slimness}}\right) \times 1.25 From similar considerations: \left({\text{enclosed-cube-} \atop \text{slimness}}\right) \leq \left({\text{enclosed-ball-} \atop \text{slimness}}\right) \times \sqrt[d]{V_d} \times \frac{\sqrt d}{2} \left({\text{enclosed-square-} \atop \text{slimness}}\right) \leq \left({\text{enclosed-disk-} \atop \text{slimness}}\right) \times 1.25 A -dimensional ball with radius is enclosed in a -dimensional cube with side-length . Hence for every -dimensional object: \left({\text{enclosing-cube-} \atop \text{slimness}}\right) \leq \left({\text{enclosing-ball-} \atop \text{slimness}}\right) \times \frac{2}{\sqrt[d]{V_d}} For even dimensions ( ), the factor simplifies to: 2 \left/ \sqrt[2k]{(k!)} \ \right/ \sqrt\pi. In particular, for two-dimensional shapes the factor is: \tfrac{2}{\sqrt\pi} \approx 1.13, so: \left({\text{enclosing-square-} \atop \text{slimness}}\right) \leq \left({\text{enclosing-disk-} \atop \text{slimness}}\right) \times 1.13 From similar considerations: \left({\text{enclosed-ball-} \atop \text{slimness}}\right) \leq \left({\text{enclosed-cube-} \atop \text{slimness}}\right) \times \frac{2}{\sqrt[d]{V_d}} \left({\text{enclosed-disk-} \atop \text{slimness}}\right) \leq \left({\text{enclosed-square-} \atop \text{slimness}}\right) \times 1.13 Multiplying the above relations gives the following simple relations: \left({\text{two-balls-} \atop \text{slimness}}\right) \leq \left({\text{two-cubes-} \atop \text{slimness}}\right) \times \sqrt{d} \left({\text{two-cubes-} \atop \text{slimness}}\right) \leq \left({\text{two-balls-} \atop \text{slimness}}\right) \times \sqrt{d} Thus, an -fat object according to the either the two-balls or the two-cubes definition is at most -fat according to the alternative definition. For example, consider a lollipop with a candy in the shape of a square and a stick in the shape of a rectangle (with ). As 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 ( ). Thus all three slimness factors are bounded: \begin{align} \left({\text{enclosing-cube-} \atop \text{slimness}}\right) &\leq 2, \\[4pt] \left({\text{enclosed-cube-} \atop \text{slimness}}\right) &\leq 2, \\[4pt] \left({\text{two-cube-} \atop \text{slimness}}\right) &= 2. \end{align} 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 by considering the set of all balls whose center is inside and whose boundary intersects the boundary of (i.e. not entirely containing ). The local-enclosing-ball-slimness factor is defined as: \frac{1}{2}\cdot \sup_{b \in B}\left(\frac{\text{volume} (B)}{\text{volume} (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 stick, and it goes to ∞ as grows. Thus by the local definition the above lollipop is not 2-fat. \begin{align} \left({\text{enclosing-ball-} \atop \text{slimness}}\right)^d &= \frac{\text{volume(smallest enclosing ball)}}{\text{volume}(o)} \\[4pt] &\leq \frac{\text{volume} (b \in B)}{\text{volume}(o)} \\[4pt] &= \frac{\text{volume} (b \in B)}{\text{volume}(b \cap o)} \\[4pt] &\leq \left[ 2 \times \left({\text{local-enclosing-} \atop \text{ball-slimness}}\right) \right]^d \end{align} Hence: \left({\text{enclosing-ball-} \atop \text{slimness}}\right) \leq \left({\text{local-enclosing-} \atop \text{ball-slimness}}\right) \times 2 For a convex body, the opposite is also true: local-fatness implies global-fatness. The proof is based on the following lemma. Let be a convex object. Let be a point in . Let and be two balls centered at such that is smaller than . Then intersects a larger portion of than of , 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 , we can look at different angles and measure the distance to the boundary of . Because is convex, this distance is a function, say . 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{\left(\frac{r(\theta)}{\text{radius} \ (b)},1 \right)} Similarly we can calculate the right-hand side of the inequality by integrating the following function: F(\theta) = \min{ \left(\frac{r(\theta)}{\text{radius} \ (B)},1 \right)} By checking all 3 possible cases, it is possible to show that always . Thus the integral of is at least the integral of , and the lemma follows. The definition of local-enclosing-ball slimness considers all balls that are centered in a point in and intersect the boundary of . However, when is convex, the above lemma allows us to consider, for each point in , only balls that are maximal in size, i.e., only balls that entirely contain (and whose boundary intersects the boundary of ). For every such ball : \text{volume} \ (b)\leq C_d\cdot \text{diameter} \ (o)^d where is some dimension-dependent constant. The diameter of is at most the diameter of the smallest ball enclosing , and the volume of that ball is: C_d \cdot \left( \frac{\text{diameter(smallest ball enclosing}\ o)}{2} \right)^d Combining all inequalities gives that for every convex object: \left({\text{local-enclosing-} \atop \text{ball-slimness}}\right) \leq \left({\text{enclosing-ball-} \atop \text{slimness}}\right) For non-convex objects, this inequality of course doesn't hold, as exemplified by the lollipop above. \Delta = r^2 \cdot \left(\cot \frac{\angle A}{2} + \cot \frac{\angle B}{2} + \cot \frac{\angle C}{2} \right) where is the area of a triangle and 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} } \Delta = R^2 \cdot 2 \sin A \sin B \sin C where again is the area of a triangle and 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 is any side of the triangle and are the adjacent angles. Hence, for an obtuse triangle with acute angles and (and longest side ), 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. \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, should be used instead of . By the law of sines: \frac{c}{2} = R \sin{\angle{C}} Hence the slimness factor of an obtuse triangle with obtuse angle 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{\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). \frac{\text{length of chord}}{\text{height of segment}} = \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{1}{\theta} For an ellipse, the slimness factors are different in different locations. For example, consider an ellipse with short axis and long axis . the length of a chord ranges between 2a\sin\tfrac{\theta}{2} at the narrow side of the ellipse and 2b\sin\tfrac{\theta}{2} at its wide side; similarly, the height of the segment ranges between b\bigl(1 - \cos\tfrac{\theta}{2}\bigr) at the narrow side and a\bigl(1 - \cos\tfrac{\theta}{2}\bigr) 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: \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) V_d \cdot \frac{(C a)^d }{V_d \cdot \frac{a^d}{R^d}} = (R C)^d For example (taking , and ): The number of non-overlapping disks with radius at least 1 contained in a circle of radius 3 is at most . (Actually, it is at most 7). If we consider local-fatness instead of global-fatness, we can get a stronger lemma: Lemma 2: Let and be two constants. Consider a collection of non-overlapping -dimensional objects that are all locally -fat (i.e. with local-enclosing-ball-slimness  ). Let be a single object in that collection with diameter . Then the number of objects in the collection with diameter larger than that lie within distance from object is at most: (4 R \cdot (C+1))^d For example (taking , and ): the number of non-overlapping disks with radius larger than 1 that touch a given unit disk is at most (this is not a tight bound since in this case it is easy to prove an upper bound of 5).

Text derived from https://en.wikipedia.org/w/index.php?oldid=1312392982 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001312392982 · captured 1758360479.0 · version history

Cite this page as: encyclopegia.org, “Fat object (geometry)”, snapshot enwiki-001312392982. https://encyclopegia.org/a/fat-object-geometry

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.