Computational geometry

Computational geometry Topics

Sort by:

Steiner's segment problem

Given points, find the line segments with the shortest possible total length which connect the points. The segments need not necessarily be straight from one point to another.For three points, if all angles are less than , then the line segments are those connecting the three points to a central point which makes the angles , , and all . If one angle is greater that , then coincides with the offending angle.For four points, is the intersection of the two diagonals, but the required minimum segments are not necessarily these diagonals.A modified version of the problem is, given two points, to find the segments with the shortest total length connecting the points such that each branch point may be connected to only three segments. There is no general solution to this version of the problem...

Triangle triangle picking

The problem of finding the mean triangle area of a triangle with vertices picked inside a triangle with unit area was proposed by Watson (1865) and solved by Sylvester. It solution is a special case of the general formula for polygon triangle picking.Since the problem is affine, it can be solved by considering for simplicity an isosceles right triangle with unit leg lengths. Integrating the formula for the area of a triangle over the six coordinates of the vertices (and normalizing to the area of the triangle and region of integration by dividing by the integral of unity over the region) gives(1)(2)where(3)is the triangle area of a triangle with vertices , , and .The integral can be solved using computer algebra by breaking up the integration region using cylindrical algebraic decomposition. This results in 62 regions, 30 of which have distinct integrals, each of which can be directly integrated. Combining the results then gives the result(4)(Pfiefer..

Tetrahedron triangle picking

Given a regular tetrahedron of unit volume, the mean triangle area of a triangle picked at random inside it is approximately , and the variance is .

Tetrahedron circumscribing

The (not necessarily regular) tetrahedron of least volume circumscribed around a convex body with volume is not known. If is a parallelepiped, then the smallest-volume tetrahedron containing it has volume 9/2. It is conjectured that this is the worst possible fit for the general problem, but this remains unproved.

Disk triangle picking

Pick three points , , and distributed independently and uniformly in a unit disk (i.e., in the interior of the unit circle). Then the average area of the triangle determined by these points is(1)Using disk point picking, this can be writtenas(2)where(3)A trigonometric substitution can then be used to remove the trigonometric functions and split the integral into(4)where(5)(6)However, the easiest way to evaluate the integral is using Crofton's formula and polar coordinates to yield a mean triangle area(7)for unit-radius disks (OEIS A189511), or(8)for unit-area disks (OEIS A093587; Woolhouse 1867; Solomon 1978; Pfiefer 1989; Zinani 2003). This problem is very closely related to Sylvester's four-point problem, and can be derived as the limit as of the general polygon triangle picking problem.The distribution of areas, illustrated above, is apparently not known exactly.The probability that three random points in a disk form an acute..

Cube triangle picking

The mean triangle area of a triangle picked at random inside a unit cube is , with variance .The distribution of areas, illustrated above, is apparently not known exactly.The probability that a random triangle in a cube is obtuse is approximately .

Square point picking

Picking two independent sets of points and from a unit uniform distribution and placing them at coordinates gives points uniformly distributed over the unit square.The distribution of distances from a randomly selected point in the unit square to its center is illustrated above.The expected distance to the square's center is(1)(2)(3)(4)(Finch 2003, p. 479; OEIS A103712), where is the universal parabolic constant. The expected distance to a fixed vertex is given by(5)(6)which is exactly twice .The expected distances from the closest and farthest vertices are given by(7)(8)Pick points at randomly in a unit square and take the convex hull . Let be the expected area of , the expected perimeter, and the expected number of vertices of . Then(9)(10)(11)(12)(13)(14)(OEIS A096428 and A096429), where is the multiplicative inverse of Gauss's constant, is the gamma function, and is the Euler-Mascheroni constant (Rényi and Sulanke..

Sphere tetrahedron picking

Sphere tetrahedron picking is the selection of quadruples of of points corresponding to vertices of a tetrahedron with vertices on the surface of a sphere. random tetrahedra can be picked on a unit sphere in the Wolfram Language using the function RandomPoint[Sphere[], n, 4].Pick four points on a sphere. What is the probability that the tetrahedron having these points as polyhedron vertices contains the center of the sphere? In the one-dimensional case, the probability that a second point is on the opposite side of 1/2 is 1/2. In the two-dimensional case, pick two points. In order for the third to form a triangle containing the center, it must lie in the quadrant bisected by a line segment passing through the center of the circle and the bisector of the two points. This happens for one quadrant, so the probability is 1/4. Similarly, for a sphere the probability is one octant, or 1/8.Pick four points at random on the surface of a unit sphereusing(1)(2)(3)with..

Simplex simplex picking

Given a simplex of unit content in Euclidean -space, pick points uniformly and independently at random, and denote the expected content of their convex hull by . Exact values are known only for and 2.(1)(2)(Buchta 1984, 1986), giving the first few values 0, 1/3, 1/2, 3/5, 2/3, 5/7, ...(OEIS A026741 and A026741).(3)(4)where is a harmonic number (Buchta 1984, 1986), giving the first few values 0, 0, 1/12, 1/6, 43/180, 3/10, 197/560, 499/1260, ... (OEIS A093762 and A093763).Not much is known about , although(5)(Buchta 1983, 1986) and(6)(Buchta 1986).Furthermore, Buchta and Reitzner (2001) give an explicit formula for the expected volume of the convex hull of points chosen at random in a three-dimensional simplex for arbitrary .

Hypercube line picking

Let two points and be picked randomly from a unit -dimensional hypercube. The expected distance between the points , i.e., the mean line segment length, is then(1)This multiple integral has been evaluated analytically only for small values of . The case corresponds to the line line picking between two random points in the interval .The first few values for are given in the following table.OEIS1--0.3333333333...2A0915050.5214054331...3A0730120.6617071822...4A1039830.7776656535...5A1039840.8785309152...6A1039850.9689420830...7A1039861.0515838734...8A1039871.1281653402...The function satisfies(2)(Anderssen et al. 1976), plotted above together with the actual values.M. Trott (pers. comm., Feb. 23, 2005) has devised an ingenious algorithm for reducing the -dimensional integral to an integral over a 1-dimensional integrand such that(3)The first few values are(4)(5)(6)(7)In the limit as , these..

Ball triangle picking

Ball triangle picking is the selection of triples of points (corresponding to vertices of a general triangle) randomly placed inside a ball. random triangles can be picked in a unit ball in the Wolfram Language using the function RandomPoint[Ball[], n, 3].The distribution of areas of a triangle with vertices picked at random in a unit ball is illustrated above. The mean triangle area is(1)(Buchta and Müller 1984, Finch 2010). random triangles can be picked in a unit ball in the Wolfram Language using the function RandomPoint[Ball[], n, 3].The determination of the probability for obtaining an acute triangle by picking three points at random in the unit disk was generalized by Hall (1982) to the -dimensional ball. Buchta (1986) subsequently gave closed form evaluations for Hall's integrals. Let be the probability that three points chosen independently and uniformly from the -ball form an acute triangle, then (2)(3)These can be combined..

Voronoi diagram

The partitioning of a plane with points into convex polygons such that each polygon contains exactly one generating point and every point in a given polygon is closer to its generating point than to any other. A Voronoi diagram is sometimes also known as a Dirichlet tessellation. The cells are called Dirichlet regions, Thiessen polytopes, or Voronoi polygons.Voronoi diagrams were considered as early at 1644 by René Descartes and were used by Dirichlet (1850) in the investigation of positive quadratic forms. They were also studied by Voronoi (1907), who extended the investigation of Voronoi diagrams to higher dimensions. They find widespread applications in areas such as computer graphics, epidemiology, geophysics, and meteorology. A particularly notable use of a Voronoi diagram was the analysis of the 1854 cholera epidemic in London, in which physician John Snow determined a strong correlation of deaths with proximity to a particular..

Vertex enumeration

A convex polyhedron is defined as the set ofsolutions to a system of linear inequalities(i.e., a matrix inequality), where is a real matrix and is a real -vector. Given and , vertex enumeration is the determination of the polyhedron's polyhedron vertices.

Triangulation

Triangulation is the division of a surface or plane polygon into a set of triangles, usually with the restriction that each triangle side is entirely shared by two adjacent triangles. It was proved in 1925 that every surface has a triangulation, but it might require an infinite number of triangles and the proof is difficult (Francis and Weeks 1999). A surface with a finite number of triangles in its triangulation is called compact.Wickham-Jones (1994) gives an algorithm for triangulation ("otectomy"), and O'Rourke (1998, p. 47) sketches a method for improving this to , as first done by Lennes (1911). Garey et al. (1978) gave an algorithmically straightforward method for triangulation, which was for many years believed optimal. However, Tarjan and van Wyk (1988) produced an algorithm. This was followed by an unexpected result due to Chazelle (1991), who showed that an arbitrary simple polygon can be triangulated in . However,..

Cube square inscribing

What is the area of the largest square that can be inscribed on a unit cube (Trott 2004, p. 104)? The answer is 9/8, given by a square with vertices (1/4, 0, 0), (0, 1, 1/4), (3/4, 1, 1), (1, 0, 3/4), or any configuration equivalent by symmetry.In general, let be the edge of the largest -dimensional cube that fits inside an -dimensional cube, with . Then(1)(2)(3)(4)(Croft et al. 1991, p. 53). For larger , little is known.

Circle triangle picking

Select three points at random on the circumference of a unit circle and find the distribution of areas of the resulting triangles determined by these three points.The first point can be assigned coordinates without loss of generality. Call the central angles from the first point to the second and third and . The range of can be restricted to because of symmetry, but can range from . Then(1)so(2)(3)Therefore,(4)(5)(6)(7)But(8)(9)(10)(11)Write (10) as(12)then(13)and(14)From (12),(15)(16)(17)(18)(19)so(20)Also,(21)(22)(23)(24)so(25)Combining (◇) and (◇) gives the meantriangle area as(26)(OEIS A093582).The first few moments are(27)(28)(29)(30)(31)(32)(OEIS A093583 and A093584and OEIS A093585 and A093586).The variance is therefore given by(33)The probability that the interior of the triangle determined by the three points picked at random on the circumference of a circle contains the origin is 1/4...

Circle point picking

A uniform distribution of points on the circumference of a circle can be obtained by picking a random real number between 0 and . Picking random points on a circle is therefore a great deal more straightforward than sphere point picking. random points can be picked on a unit circle in the Wolfram Language using the function RandomPoint[Circle[], n].Random points on a circle can also be obtained by picking two numbers , from a uniform distribution on , and rejecting pairs with . From the remaining points, the double-angle formulas then imply that the points with Cartesian coordinates(1)(2)have the desired distribution (von Neumann 1951, Cook 1957). This method can also be extended to sphere point picking (Cook 1957). The plots above show the distribution of points for 50, 100, and 500 initial points (where the counts refer to the number of points before throwing away)...

Circle line picking

Given a unit circle, pick two points at random on its circumference, forming a chord. Without loss of generality, the first point can be taken as , and the second by , with (by symmetry, the range can be limited to instead of ). The distance between the two points is then(1)The average distance is then given by(2)The probability density function is obtained from(3)The raw moments are then(4)(5)(6)giving the first few as(7)(8)(9)(10)(11)(OEIS A000984 and OEIS A093581 and A001803), where the numerators of the odd terms are 4 times OEIS A061549.The central moments are(12)(13)(14)giving the skewness and kurtosisexcess as(15)(16)Bertrand's problem asks for the probability that a chord drawn at random on a circle of radius has length .

Circle covering by arcs

The probability that random arcs of angular size cover the circumference of a circle completely (for a circle with unit circumference) iswhere is the floor function (Solomon 1978, p. 75). This was first given correctly by Stevens (1939), although partial results were obtains by Whitworth (1897), Baticle (1935), Garwood (1940), Darling (1953), and Shepp (1972).The probability that arcs leave exactly gaps is given by(Stevens 1939; Solomon 1978, pp. 75-76).

Tetrahedron tetrahedron picking

The mean tetrahedron volume of a tetrahedron with vertices chosen at random inside another tetrahedron of unit volume is given by(1)(2)(OEIS A093525; Buchta and Reitzner 1992; Mannion1994; Schneider 1997, p. 170; Buchta and Reitzner 2001; Zinani 2003).This provides a disproof of the conjecture that the solution to this problem is a rational number (1/57 had been suggested by Croft et al. 1991, p. 54), and renders obsolete Solomon's statement that "Explicit values for random points in non-spherical regions such as tetrahedrons, parallelepipeds, etc., have apparently not yet been successfully calculated" (Solomon 1978, p. 124).Furthermore, Buchta and Reitzner (2001) give an explicit formula for the expected volume of the convex hull of points chosen at random in a three-dimensional simplex for arbitrary ...

Heilbronn triangle problem

The Heilbronn triangle problem is to place points in a disk (square, equilateral triangle, etc.) of unit area so as to maximize the area of the smallest of the triangles determined by the points. For points, there is only a single triangle, so Heilbronn's problem degenerates into finding the largest triangle that can be constructed from points in a square. For , there are four possible triangles for each configuration, so the problem is to find the configuration of points for which the smallest of these four triangles is the maximum possible.For a unit square, the first few maxima of minimaltriangle areas are(1)(2)(3)(4)(5)(6)(7)(8)For larger values of , proofs of optimality are open, but the best known results are(9)(10)(11)(12)(13)(14)(15)(16)(17)(18)(19)(20)(21)(22)(23)(24)(25)(26)(27)with the configurations leading to maximum minimal triangles illustrated above (Friedman 2006; Comellas and Yebra 2002; D. Cantrell..

Line segment picking

Line segment picking is the process of picking line segments at random within a given shape in the plane, in space, or in a higher dimension. The most natural definition of a random line segment is one such that the position of each endpoint has a uniform distribution within the shape. In the case of convex shapes, any line segment so picked lies entirely inside the shape.It is possible to compute the mean line segment length in closed form for some simple shapes. In some cases, a closed form can also be obtained for the full probability density function of line segment lengths.

Mean line segment length

The mean line segment length is the average length of a line segment in line segment picking within some given shape. As summarized in the following table (where denotes the Robbins constant and its generalization to dimension ), it is possible to compute the mean line segment length in closed form for line segment picking for some simple shapes. In some cases, a closed form can also be obtained for the probability density function of line segment lengths.shape3,4,5 triangle line picking30-60-90 triangle line pickingball line pickingcircle line pickingcube line pickingdisk line pickingequilateral triangle line pickinghypercube line pickingisosceles right triangle line pickingline line pickingsphere line pickingsquare line pickingtetrahedron line picking

Happy end problem

The happy end problem, also called the "happy ending problem," is the problem of determining for the smallest number of points in general position in the plane (i.e., no three of which are collinear), such that every possible arrangement of points will always contain at least one set of points that are the vertices of a convex polygon of sides. The problem was so-named by Erdős when two investigators who first worked on the problem, Ester Klein and George Szekeres, became engaged and subsequently married (Hoffman 1998, p. 76).Since three noncollinear points always determine a triangle, .Random arrangements of points are illustrated above. Note that no convex quadrilaterals are possible for the arrangements shown in the fifth and eighth figures above, so must be greater than 4. E. Klein proved that by showing that any arrangement of five points must fall into one of the three cases (left top figure; Hoffman 1998,..

Geometric span

The geometric span is largest possible distance between two points drawn from a finite set of points. It is therefore closely related to the generalized diameter of a closed figure.Jung's theorem states that every finite set of points with geometric span has an enclosing circle with radius no greater than .

Moving sofa problem

What is the sofa of greatest area which can be moved around a right-angled hallway of unit width? Hammersley (Croft et al. 1994) showed that(1)(OEIS A086118). Gerver (1992) found a sofa with larger area and provided arguments indicating that it is either optimal or close to it. The boundary of Gerver's sofa is a complicated shape composed of 18 arcs. Its area can be given by defining the constants , , , and by solving(2)(3)(4)(5)This gives(6)(7)(8)(9)Now define(10)where(11)(12)(13)Finally, define the functions(14)(15)(16)The area of the optimal sofa is then given by(17)(18)(Finch 2003).

Hermite constants

The Hermite constant is defined for dimension as the value(1)(Le Lionnais 1983). In other words, they are given by(2)where is the maximum lattice packing density for hypersphere packing and is the content of the -hypersphere. The first few values of are 1, 4/3, 2, 4, 8, 64/3, 64, 256, ... (OEIS A007361 and A007362; Gruber and Lekkerkerker 1987, p. 518). Values for larger are not known.For sufficiently large ,(3)

Groemer theorem

Given circles and a perimeter , the total area of the convex hull isFurthermore, the actual area equals this value iff the packing is a Groemer packing. The theorem was proved in 1960 by Helmut Groemer.

Square packing

Find the minimum size square capable of bounding equal squares arranged in any configuration. The first few cases are illustrated above (Friedman). The only packings which have been proven optimal are 2, 3, 5, 6, 7, 8, 14, 15, 24, and 35, in addition to the trivial cases of the square numbers (Friedman).If for some , it is conjectured that the size of the minimum bounding square is for small . The smallest for which the conjecture is known to be violated is (with ).The following table gives the smallest known side lengths for a square into which unit squares can be packed (Friedman 2005). An asterisk (*)indicates that a packing has been proven to be optimal.exactapprox.exactapprox.1*1116*442*22174.6755...3*22184.822...4*22194.885...5*2.707...20556*3321557*3322558*3323*559*3324*5510*3.707...25*55113.877...265.6214...1244275.7072...1344285.8285...14*44295.9465...15*44The best known packings of squares into a circle..

Dodecahedral conjecture

The kissing number of a sphere is 12. This led Fejes Tóth (1943) to conjecture that in any unit sphere packing, the volume of any Voronoi cell around any sphere is at least as large as a regular dodecahedron of inradius 1. This statement is now known as the dodecahedral conjecture. It implies a bound of on the packing density for sphere packing, and thus provides a bound on the densest possible sphere packing. It is not, however, sufficient to establish the Kepler conjecture (which implies ).This long-outstanding conjecture was proved by Hales and McLaughlin (2002) using techniques of interval arithmetic and linear programming.

Spherical code

How can points be distributed on a unit sphere such that they maximize the minimum distance between any pair of points? This maximum distance is called the covering radius, and the configuration is called a spherical code (or spherical packing). In 1943, Fejes Tóth proved that for points, there always exist two points whose distance is(1)and that the limit is exact for , 4, 6, and 12. The problem of spherical packing is therefore sometimes known as the Fejes Tóth's problem. The general problem has not been solved.Spherical codes are similar to the Thomson problem, which seeks the stable equilibrium positions of classical electrons constrained to move on the surface of a sphere and repelling each other by an inverse square law.An approximate spherical code for points may be obtained in the Wolfram Language using the function SpherePoints[n].For two points, the points should be at opposite ends of a diameter. For four points, they..

De bruijn's theorem

A box can be packed with a harmonic brick iff the box has dimensions for some natural numbers , , (i.e., the box is a multiple of the brick).

Smoothed octagon

A plane shape constructed by Reinhardt (1934) that is conjectured to be the "worst" packer of all centrally-symmetric plane regions. It has a packing density of(OEIS A093767), significantly less than thecircle packing density of(OEIS A093766). The smoothed octagon is constructed from a regular octagon by smoothing the edges using a hyperbola that is tangent to adjacent edges of the octagon and has the edges adjacent to these as asymptotes.

Sausage conjecture

In dimensions for the arrangement of hyperspheres whose convex hull has minimal content is always a "sausage" (a set of hyperspheres arranged with centers along a line), independent of the number of -spheres. The conjecture was proposed by Fejes Tóth, and solved for dimensions by Betke et al. (1994) and Betke and Henk (1998).

Rigid circle packing

A circle packing is called rigid (or "stable") if every circle is fixed by its neighbors, i.e., no circle can be translated without disturbing other circles of the packing (e.g., Niggli 1927, Niggli 1928, Fejes Tóth 1960/61). Böröczky (1964) exhibited stable systems of congruent unit circles with density 0. A rigid packing of circles can be obtained from a hexagonal tessellation by removing the centers of a hexagonal web, then replacing each remaining circle with three equal inscribed circles (appropriately oriented), as illustrated above (Meschkowski 1966, Wells 1991).

Circle packing

A circle packing is an arrangement of circles inside a given boundary such that no two overlap and some (or all) of them are mutually tangent. The generalization to spheres is called a sphere packing. Tessellations of regular polygons correspond to particular circle packings (Williams 1979, pp. 35-41). There is a well-developed theory of circle packing in the context of discrete conformal mapping (Stephenson).The densest packing of circles in the plane is the hexagonal lattice of the bee's honeycomb (right figure; Steinhaus 1999, p. 202), which has a packing density of(1)(OEIS A093766; Wells 1986, p. 30). Gauss proved that the hexagonal lattice is the densest plane lattice packing, and in 1940, L. Fejes Tóth proved that the hexagonal lattice is indeed the densest of all possible plane packings.Surprisingly, the circular disk is not the least economical region for packing the plane. The "worst"..

Lebesgue minimal problem

Find the plane lamina of least area which is capable of covering any plane figure of unit generalized diameter. A unit circle is too small, but a hexagon circumscribed on the unit circle is larger than necessary. Pál (1920) showed that the hexagon can be reduced by cutting off two isosceles triangles on the corners of the hexagon which are tangent to the hexagon's incircle (Wells 1991; left figure above). Sprague subsequently demonstrated that an additional small curvilinear region could be removed (Wells 1991; right figure above). These constructions give upper bounds.The hexagon having inradius (giving a diameter of 1) has side length(1)and the area of this hexagon is(2)(OEIS A010527).In the above figure, the sagitta is given by(3)(4)and the other distances by(5)(6)so the area of one of the equilateral triangles removed in Pál's reduction is(7)(8)(9)(10)so the area left after removing two of these triangles is(11)(12)(13)(OEIS..

Peg

The answer to the question "which fits better, a round peg in a square hole, or a square peg in a round hole?" can be interpreted as asking which is larger, the ratio of the area of a circle to its circumscribed square, or the area of the square to its circumscribed circle? In two dimensions, the ratios are and , respectively. Therefore, a round peg fits better into a square hole than a square peg fits into a round hole (Wells 1986, p. 74).However, this result is true only in dimensions , and for , the unit -hypercube fits more closely into the -hypersphere than vice versa (Singmaster 1964; Wells 1986, p. 74). This can be demonstrated by noting that the formulas for the content of the unit -ball, the content of its circumscribed hypercube, and the content of its inscribed hypercube are given by(1)(2)(3)The ratios in question are then(4)(5)(Singmaster 1964). The ratio of these ratios is the transcendental equation(6)illustrated..

Kelvin's conjecture

What space-filling arrangement of similar cells of equal volume has minimal surface area? This questions arises naturally in the theory of foams when the liquid content is small. Kelvin (Thomson 1887) proposed that the solution was a 14-sided truncated octahedron having a very slight curvature of the hexagonal faces.The isoperimetric quotient the uncurved truncated octahedron is given by(1)(2)(3)while Kelvin's slightly curved variant has a slightly less optimal quotient of 0.757.Despite one hundred years of failed attempts and Weyl's (1952) opinion that the curved truncated octahedron could not be improved upon, Weaire and Phelan (1994) discovered a space-filling unit cell consisting of six 14-sided polyhedra and two 12-sided polyhedra with irregular faces and only hexagonal faces remaining planar. This structure has an isoperimetric quotient of 0.765, or approximately 1.0% more than Kelvin's cell.The building for water events..

Consider three mutually tangent circles, and draw their inner Soddy circle. Then draw the inner Soddy circles of this circle with each pair of the original three, and continue iteratively. The steps in the process are illustrated above (Trott 2004, pp. 34-35).An animation illustrating the construction of the gasket is shown above.The points which are never inside a circle form a set of measure 0 having fractal dimension approximately 1.3058 (Mandelbrot 1983, p. 172). The Apollonian gasket corresponds to a limit set that is invariant under a Kleinian group (Wolfram 2002, p. 986).The Apollonian gasket can also be generalized to three dimensions (Boyd 1973, Andrade et al. 2005), as illustrated above. A graph obtained by connecting the centers of touching spheres in a three-dimensional Apollonian gasket by edges is known as an Apollonian network...

Biggest little polygon

The biggest little polygon with sides is the convex plane -gon of unit polygon diameter having largest possible area.Reinhardt (1922) showed that for odd, the regular polygon on sides is the biggest little -gon. For , the square with diagonal 1 has maximum area, but an infinite number of other 4-gons are equally large (Audet et al. 2002). The case was solved by Graham (1975) and is known as Graham's biggest little hexagon, and the case was solved by Audet et al. (2002). The following table summarizes these results, showing the percentage that the given polygon is larger than the regular -gon.area% larger than regular -gonreference60.6749813.92%Graham (1975)80.7268672.79%Audet et al. (2002)The biggest little polygon graphs on and 8 nodes are implemented in the Wolfram Language as GraphData["BiggestLittlePolygon", n]...