Computational geometry

Math Topics A - Z listing

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

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

Delaunay triangulation

The Delaunay triangulation is a triangulation which is equivalent to the nerve of the cells in a Voronoi diagram, i.e., that triangulation of the convex hull of the points in the diagram in which every circumcircle of a triangle is an empty circle (Okabe et al. 1992, p. 94).The Wolfram Language command PlanarGraphPlot[pts] in the Wolfram Language package ComputationalGeometry` plots the Delaunay triangulation of the given list of points. Qhull may be used to compute these structures efficiently.The Delaunay triangulation and Voronoi diagram in are dual to each other.

Triangle point picking

Given a triangle with one vertex at the origin and the others at positions and , one might think that a random point inside the triangle would be given by(1)where and are uniform variates in the interval . However, as can be seen in the plot above, this samples the triangle nonuniformly, concentrating points in the corner.Randomly picking each of the trilinear coordinates from a uniform distribution also does not produce a uniform point spacing on in the triangle. As illustrated above, the resulting points are concentrated towards the center.To pick points uniformly distributed inside the triangle, instead pick(2)where and are uniform variates in the interval , which gives points uniformly distributed in a quadrilateral (left figure). The points not in the triangle interior can then either be discarded, or transformed into the corresponding point inside the triangle (right figure).The expected distance of a point picked at random inside..

Pentagon triangle picking

Given a regular pentagon of unit area, mean triangle area of a triangle picked at random inside it is given by the case of polygon triangle picking,(1)(2)The distribution of areas, illustrated above, is apparently not known exactly.

Cube tetrahedron picking

Given four points chosen at random inside a unit cube, the average volume of the tetrahedron determined by these points is given by(1)where the polyhedron vertices are located at where , ..., 4, and the (signed) volume is given by the determinant(2)The integral is extremely difficult to compute, but the analytic result for the mean tetrahedron volume is(3)(OEIS A093524; Zinani 2003). Note that the result quoted in the reply to Seidov (2000) actually refers to the average volume for tetrahedron tetrahedron picking.

Triangle line picking

Consider the average length of a line segment determined by two points picked at random in the interior of an arbitrary triangle. This problem is not affine, so a simple formula in terms of the area or linear properties of the original triangle apparently does not exist.However, if the original triangle is chosen to be an isosceles right triangle with unit legs, then the average length of a line with endpoints chosen at random inside it is given by(1)(2)(3)(OEIS A093063; M. Trott, pers. comm., Mar. 10, 2004), which is numerically surprisingly close to .Similarly, if the original triangle is chosen to be an equilateral triangle with unit side lengths, then the average length of a line with endpoints chosen at random inside it is given by(4)(5)The integrand can be split up into the four pieces(6)(7)(8)(9)As illustrated above, symmetry immediately gives and , so(10)With some effort, the integrals and can be done analytically to give..

Cube point picking

Cube point picking is the three-dimensional case of hypercubepoint picking.The average distance from a point picked at random inside a unitcube to the center is given by(1)(2)(3)(4)Similarly, the average distance from a point picked at random to a fixed corner is given by(5)(6)(7)(8)(9)where is the -box integral.The average distance from the center of a unit cube to a given face is(10)(11)(12)(13)(OEIS A097047).

Triangle circumscribing

Every convex body in the Euclidean plane with area can be inscribed in a triangle of area at most equal to (Gross 1918, Eggleston 1957). The worst possible fit corresponds (exclusively) to the case that is a parallelogram.

Mean triangle area

The mean triangle area is the average area of a triangle in triangle picking within some given shape. As summarized in the following table, it is possible to compute the mean triangle area in closed form for triangle picking for some simple shapes. shapeball triangle pickingcircle triangle pickingdecagon triangle pickingdisk triangle pickingequilateral triangle triangle pickinghexagon triangle pickingoctagon triangle pickingpentagon triangle pickingsquare triangle pickingtetrahedron triangle picking

Cube line picking--face and interior

Consider the distribution of distances between a point picked at random in the interior of a unit cube and on a face of the cube. The probability function, illustrated above, was found in (nearly) closed form by Mathai et al. (1999). After simplifying, correcting typos, and completing the integrals, gives the closed form(1)The first even raw moments for , 2, 4, ... are 1, 2/3, 11/18, 211/315, 187/225, 11798/10395, ....

Mean tetrahedron volume

The mean tetrahedron volume is the average volume of a tetrahedron in tetrahedron picking within some given shape. As summarized in the following table, it is possible to compute the mean tetrahedron volume in closed form for tetrahedron picking for some simple shapes.shapeball tetrahedron pickingcube tetrahedron pickingoctahedron tetrahedron pickingsphere tetrahedron pickingtetrahedron tetrahedron picking

Cube line picking--face and face

Instead of picking two points from the interior of the cube, instead pick two points on different faces of the unit cube. In this case, the average distance between the points is(1)(OEIS A093066; Borwein and Bailey 2003, p. 26;Borwein et al. 2004, pp. 66-67). Interestingly,(2)as apparently first noted by M. Trott (pers. comm., Mar. 21, 2008).The two integrals above can be written in terms of sums as(3)(4)(Borwein et al. 2004, p. 67), where however appears to be classically divergent and perhaps must be interpreted in some regularized sense.Consider a line whose endpoints are picked at random on opposite sides of the unit cube. The probability density function for the length of this line is given by(5)(Mathai 1999; after simplification). The mean length is(6)(7)The first even raw moments for , 2, 4, ... are 1, 4/3, 167/90, 284/105, 931/225, 9868/1485, ....Consider a line whose endpoints are picked at random..

Cube line picking

The average distance between two points chosen at random inside a unit cube (the case of hypercube line picking), sometimes known as the Robbins constant, is(1)(2)(3)(OEIS A073012; Robbins 1978, Le Lionnais 1983).The probability function as a function of line length, illustrated above, was found in (nearly) closed form by Mathai et al. (1999). After simplifying, correcting typos, and completing the integrals, gives the closed form(4)The first even raw moments for , 2, ... are 1, 1/2, 11/30, 211/630, 187/525, 3524083/6306300, ... (OEIS A160693 and A160694).Pick points on a cube, and space them as far apart as possible. The best value known for the minimum straight line distance between any two points is given in the following table. 51.118033988749861.0606601482100718190.86602540378463100.74999998333331110.70961617562351120.70710678118660130.70710678118660140.70710678118660150.625..

Crofton's integrals

Consider a convex plane curve with perimeter , and the set of points exterior to . Further, let and be the perpendicular distances from to (with corresponding tangent points and on ), and let . Then(1)(Crofton 1885; Solomon 1978, p. 28).If has a continuous radius of curvature and the radii of curvature at points and are and , then(2)(Solomon 1978, p. 28), and furthermore(3)(Santaló 1953; Solomon 1978, p. 28).

Hypersphere point picking

Marsaglia (1972) has given a simple method for selecting points with a uniform distribution on the surface of a 4-sphere. This is accomplished by picking two pairs of points and , rejecting any points for which and . Then the points(1)(2)(3)(4)have a uniform distribution on the surface of the hypersphere. This extends the method of Marsaglia (1972) for sphere point picking, but unfortunately does not generalize to higher dimensions.An easy way to pick a random point on a hypersphere of arbitrary dimension is to generate Gaussian random variables , , ..., . Then the distribution of the vectors(5)is uniform over the surface (Muller 1959, Marsaglia 1972).

Circular sector line picking

Pick two points at random in a circular sector of radius 1 and central angle , and consider the length of the line joining them. The following table summarizes approximate values of the mean for various . The case corresponds to disk line picking.OEIS0.47387...A1302040.70605...A1302030.90541...A093070

Square triangle picking

Square triangle picking is the selection of triples of points (corresponding to endpoints of a triangle) randomly placed inside a square. random triangles can be picked in a unit square in the Wolfram Language using the function RandomPoint[Rectangle[], n, 3].Given three points chosen at random inside a unit square, the average area of the triangle determined by these points is given analytically by the multiple integrals(1)(2)Here, represent the polygon vertices of the triangle for , 2, 3, and the (signed) area of these triangles is given by the determinant(3)(4)The solution was first given by Woolhouse (1867). Since attempting to do the integrals by brute force result in intractable integrands, the best approach using computer algebra is to divide the six-dimensional region of integration into subregions using cylindrical algebraic decomposition such that the sign of does not change, do the integral in each region directly, and then..

Square line picking

Square line picking is the selection of pairs of points (corresponding to endpoints of a line segment) randomly placed inside a square. random line segments can be picked in a unit square in the Wolfram Language using the function RandomPoint[Rectangle[], n, 2].Picking two points at random from the interior of a unit square, the average distance between them is the case of hypercube line picking, i.e.,(1)(2)(3)(OEIS A091505).The exact probability function is given by(4)(M. Trott, pers. comm., Mar. 11, 2004), and the corresponding distribution function by(5)From this, the mean distance can be computed, as can the variance of lengths,(6)(7)The statistical median is given by the rootof the quartic equation(8)which is approximately .The th raw moment is given for , 4, 6, ... as 1/3, 17/90, 29/210, 187/1575, 239/207, ... (OEIS A103304 and A103305).If, instead of picking two points from the interior of a square, two points are..

Hexagon triangle picking

The mean triangle area of a triangle picked inside a regular hexagon with unit area is (Woolhouse 1867, Pfiefer 1989). This is a special case of a general polygon triangle picking result due to Alikoski (1939).The distribution of areas, illustrated above, is apparently not known exactly.

Sphere point picking

To pick a random point on the surface of a unit sphere, it is incorrect to select spherical coordinates and from uniform distributions and , since the area element is a function of , and hence points picked in this way will be "bunched" near the poles (left figure above). random points can be picked on a unit sphere in the Wolfram Language using the function RandomPoint[Sphere[], n].To obtain points such that any small area on the sphere is expected to contain the same number of points (right figure above), choose and to be random variates on . Then(1)(2)gives the spherical coordinates for a set of points which are uniformly distributed over . This works since the differential element of solid angle is given by(3)The distribution of polar angles can be found from(4)by taking the derivative of (2) with respect to to get , solving (2) for , and plugging the results back in to (4) with to obtain the distribution(5)Similarly, we can pick to be uniformly..

Sphere line picking

Sphere line picking is the selection of pairs of points corresponding to vertices of a line segment with endpoints on the surface of a sphere. random line segments can be picked on a unit sphere in the Wolfram Language using the function RandomPoint[Sphere[], n, 2].Pick two points at random on a unit sphere. The first one can be placed at the north pole, i.e., assigned the coordinate (0, 0, 1), without loss of generality. The second point is then chosen at random using sphere point picking, and so can be assigned coordinates(1)(2)(3)with and . The distance between first and second points is then(4)and solving for gives(5)Now the probability function for distance is then given by(6)(Solomon 1978, p. 163), since and . Here, .Therefore, somewhat surprisingly, large distances are the most common, contrary to most people's intuition. A plot of 15 random lines is shown above. The raw moments are(7)giving the first few as(8)(9)(10)(11)(OEIS..

Geometric probability

The study of the probabilities involved in geometric problems, e.g., the distributions of length, area, volume, etc. for geometric objects under stated conditions.The following table summarized known results for picking geometric objects from points in or on the boundary of other geometric objects, where is the Robbins constant.type of selectionquantitymeandistribution known?point probability known?line line pickinglengthyes-isosceles triangle line pickinglength-equilateral triangle line pickinglength-square line pickinglengthyes-circle line pickinglengthyes-disk line pickinglengthyes-tetrahedron line pickinglength?-cube line pickinglengthyes-triangle triangle pickingareasquare triangle pickingareayesyespentagon triangle pickingareahexagon triangle pickingareacircle triangle pickingareadisk triangle pickingareatetrahedron triangle pickingarea?-cube triangle pickingarea?-ball..

Bertrand's problem

What is the probability that a chord drawn at random on a circle of radius (i.e., circle line picking) has length (or sometimes greater than or equal to the side length of an inscribed equilateral triangle; Solomon 1978, p. 2)? The answer depends on the interpretation of "two points drawn at random," or more specifically on the "natural" measure for the problem.In the most commonly considered measure, the angles and are picked at random on the circumference of the circle. Without loss of generality, this can be formulated as the probability that the chord length of a single point at random angle measured from the intersection of the positive x-axis along the unit circle. Since the length as a function of (circle line picking) is given by(1)solving for gives , so the fraction of the top unit semicircle having chord length greater than 1 is(2)However, if a point is instead placed at random on a radius of the circle and a chord..

Gaussian triangle picking

Finch (2010) gives an overview of known results for random Gaussian triangles.Let the vertices of a triangle in dimensions be normal (normal) variates. The probability that a Gaussian triangle in dimensions is obtuse is(1)(2)(3)(4)(5)where is the gamma function, is the hypergeometric function, and is an incomplete beta function.For even ,(6)(Eisenberg and Sullivan 1996).The first few cases are explicitly(7)(8)(9)(10)(OEIS A102519 and A102520). The even cases are therefore 3/4, 15/32, 159/512, 867/4096, ... (OEIS A102556 and A102557) and the odd cases are , where , 9/8, 27/20, 837/560, ... (OEIS A102558 and A102559).

Robbins constant

The Robbins constant is the mean line segment length, i.e., the expected distance between two points chosen at random in cube line picking, namely(1)(2)(3)(OEIS A073012; Robbins 1978, Le Lionnais 1983).

Ball tetrahedron picking

Ball tetrahedron picking is the selection of quadruples of points (corresponding to vertices of a general tetrahedron) randomly placed inside a ball. random tetrahedra can be picked in a unit ball in the Wolfram Language using the function RandomPoint[Ball[], n, 4].The mean tetrahedron volume of a tetrahedronformed by four random points in a unit ball is(OEIS A093591; Hostinsky 1925; Solomon 1978,p. 124; Zinani 2003).

Ball point picking

Ball point picking is the selection of points randomly placed inside a ball. random points can be picked in a unit ball in the Wolfram Language using the function RandomPoint[Ball[], n].Pick variates , ..., independently from a standard normal distribution and variate independently from an exponential distribution with parameter . Then the distribution of points(1)is uniform over the unit -ball. Note however that in practice, computation of points inside a unit -ball may still be slower using this technique than computing additional points (e.g., by a factor of for and for ) inside an -cube of edge length 2 and discarding the ones with norm greater than 1.This result is a special case of a beautiful general result described by Barthe (et al. 2005) which may be stated as follows. For and a sequence of real numbers , define the -norm as(2)The space of all infinite sequences with is then denoted , and the space equipped with quasi-norm is denoted . Finally,..

Disk point picking

To generate random points over the unit disk, it is incorrect to use two uniformly distributed variables and and then take(1)(2)Because the area element is given by(3)this gives a concentration of points in the center (left figure above).The correct transformation is instead given by(4)(5)(right figure above).The probability function for distance from the center of a point picked at random in a unit disk is(6)The raw moments are therefore given by(7)giving a mean distance of .

Ball line picking

Given an -ball of radius , find the distribution of the lengths of the lines determined by two points chosen at random within the ball. The probability distribution of lengths is given by(1)where(2)and(3)is a regularized beta function, with is an incomplete beta function and is a beta function (Tu and Fischbach 2000).The first few are(4)(5)(6)(7)The mean line segment lengths for and the first few dimensions are given by(8)(9)(10)(11)(OEIS A093530 and A093531 and OEIS A093532 and A093533), corresponding to line line picking, disk line picking, (3-D) ball line picking, and so on.

Polygon triangle picking

The mean triangle area of a triangle picked inside a regular -gon of unit area is(1)where (Alikoski 1939; Solomon 1978, p. 109; Croft et al. 1991, p. 54). Prior to Alikoski's work, only the special cases , 4, 6, 8, and had been determined. The first few cases are summarized in the following table, where is the largest root of(2)and is the largest root of(3)problem3triangle triangle picking4square triangle picking5pentagon triangle picking6hexagon triangle picking78910Amazingly, the algebraic degree of is equal to , where is the totient function, giving the first few terms for , 4, ... as 1, 1, 2, 1, 3, 2, 3, 2, 5, 2, 6, 3, 4, 4, 8, ... (OEIS A023022). Therefore, the only values of for which is rational are , 4, and 6.

Disk line picking

Using disk point picking,(1)(2)for , , choose two points at random in a unit disk and find the distribution of distances between the two points. Without loss of generality, take the first point as and the second point as . Then(3)(4)(5)(6)(OEIS A093070; Uspensky 1937, p. 258;Solomon 1978, p. 36).This is a special case of ball line picking with , so the full probability function for a disk of radius is(7)(Solomon 1978, p. 129).The raw moments of the distribution of line lengthsare given by(8)(9)where is the gamma function and . The expected value of is given by , giving(10)(Solomon 1978, p. 36). The first few moments are then(11)(12)(13)(14)(15)(16)(OEIS A093526 and A093527 and OEIS A093528 and A093529). The moments that are integers occur at , 2, 6, 15, 20, 28, 42, 45, 66, ... (OEIS A014847), which rather amazingly are exactly the values of such that , where is a Catalan number (E. Weisstein, Mar. 30, 2004)...

Nearest neighbor problem

The problem in computational geometry of identifying the point from a set of points which is nearest to a given point according to some measure of distance. The nearest neighborhood problem involves identifying the locus of points lying nearer to the query point than to any other point in the set.The nearest neighbor from the set of points , can be computed in the Wolfram Language using Nearest[u1, u2, ..., , x].An extensive site of nearest neighbor material is maintained by Lifshits.

Radon's theorem

Any set of points in can always be partitioned in two subsets and such that the convex hulls of and intersect.

Convex hull

The convex hull of a set of points in dimensions is the intersection of all convex sets containing . For points , ..., , the convex hull is then given by the expressionComputing the convex hull is a problem in computational geometry. The indices of the points specifying the convex hull of a set of points in two dimensions is given by the command ConvexHull[pts] in the Wolfram Language package ComputationalGeometry` . Future versions of the Wolfram Language will support three-dimensional convex hulls. A makeshift package for computing three-dimensional convex hulls in the Wolfram Language has been written by Meeussen and Weisstein.In dimensions, the "gift wrapping" algorithm, which has complexity , where is the floor function, can be used (Skiena 1997, p. 352). In two and three dimensions, however, specialized algorithms exist with complexity (Skiena 1997, pp. 351-352). Yao (1981) has proved that any decision-tree..

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

Apollonian gasket

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

Subscribe to our updates
79 345 subscribers already with us
Math Subcategories
Check the price
for your project