text:
# Euclidean minimum spanning tree

Euclidean minimum spanning tree of 25 random points in the plane

A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.

The edges of the minimum spanning tree meet at angles of at least 60°, at most six to a vertex. In higher dimensions, the number of edges per vertex is bounded by the kissing number of tangent unit spheres. The total length of the edges, for points in a unit square, is at most proportional to the square root of the number of points. Each edge lies in an empty region of the plane, and these regions can be used to prove that the Euclidean minimum spanning tree is a subgraph of other geometric graphs including the relative neighborhood graph and Delaunay triangulation. By constructing the Delaunay triangulation and then applying a graph minimum spanning tree algorithm, the minimum spanning tree of ${\displaystyle n}$ given planar points may be found in time ${\displaystyle O(n\log n)}$, as expressed in big O notation. This is optimal in some models of computation, although faster randomized algorithms exist for points with integer coordinates. For points in higher dimensions, finding an optimal algorithm remains an open problem.

## Definition and related problems

A Euclidean minimum spanning tree, for a set of ${\displaystyle n}$ points in the Euclidean plane or Euclidean space, is a system of line segments, having only the given points as their endpoints, whose union includes all of the points in a connected set, and which has the minimum possible total length of any such system. Such a network cannot contain a polygonal ring of segments; if one existed, the network could be shortened by removing an edge of the polygon. Therefore, the minimum-length network forms a tree. This observation leads to the equivalent definition that a Euclidean minimum spanning tree is a tree of line segments between pairs of the given points, of minimum total length.[1] The same tree may also be described as a minimum spanning tree of a weighted complete graph, having the given points as its vertices and the distances between points as edge weights.[2] The same points may have more than one minimum spanning tree. For instance, for the vertices of a regular polygon, removing any edge of the polygon produces a minimum spanning tree.[3]

Publications on the Euclidean minimum spanning tree commonly abbreviate it as "EMST".[4][5] They may also be called "geometric minimum spanning trees",[6][7] but that term may be used more generally for geometric spaces with non-Euclidean distances, such as Lp spaces.[8] When the context of Euclidean point sets is clear, they may be called simply "minimum spanning trees".[9][10][11]

Several other standard geometric networks are closely related to the Euclidean minimum spanning tree:

• The Steiner tree problem again seeks a system of line segments connecting all given points, but without requiring the segments to start and end only at given points. In this problem, additional points may be added as segment endpoints, allowing the Steiner tree to be shorter than the minimum spanning tree.[12]
• In the Euclidean traveling salesperson path problem, the connecting line segments must start and end at the given points, like the spanning tree and unlike the Steiner tree; additionally, each point can touch at most two line segments, so the result forms a polygonal chain. Because of this restriction, the optimal path may be longer than the Euclidean minimum spanning tree, but is at most twice as long.[2]
• Geometric spanners are low-weight networks that, like the minimum spanning tree, connect all of the points. Unlike the minimum spanning tree, all of these connecting paths are required to be short, having length proportional to the distance between the points they connect. To achieve this property, these networks generally have cycles and so are not trees.[13]

## Properties

### Angles and vertex degrees

Twelve unit spheres all tangent to a central unit sphere. The minimum spanning tree of their 13 center points has degree 12 at the central point.

Whenever two edges of a Euclidean minimum spanning tree meet at a vertex, they must form an angle of 60° or more, with equality only when they form two sides of an equilateral triangle. This is because, for two edges forming any sharper angle, one of the two edges could be replaced by the third, shorter edge of the triangle they form, forming a tree with smaller total length.[14] In comparison, the Steiner tree problem has a stronger angle bound: an optimal Steiner tree has all angles at least 120°.[12]

The same 60° angle bound also occurs in the kissing number problem, of finding the maximum number of unit spheres in Euclidean space that can be tangent to a central unit sphere without any two spheres intersecting (beyond a point of tangency). The center points of these spheres have a minimum spanning tree in the form of a star, with the central point adjacent to all other points. Conversely, for any vertex ${\displaystyle v}$ of any minimum spanning tree, one can construct non-overlapping unit spheres centered at ${\displaystyle v}$ and at points two units along each of its edges, with a tangency for each neighbor of ${\displaystyle v}$. Therefore, in ${\displaystyle n}$-dimensional space the maximum possible degree of a vertex (the number of spanning tree edges connected to it) equals the kissing number of spheres in ${\displaystyle n}$ dimensions.[15] Planar minimum spanning trees have degree at most six, and when a tree has degree six there is always another minimum spanning tree with maximum degree five.[7] Three-dimensional minimum spanning trees have degree at most twelve.[15] The only higher dimensions in which the exact value of the kissing number is known are four, eight, and 24 dimensions.[16]

For points generated at random from a given continuous distribution, the minimum spanning tree is almost surely unique. The numbers of vertices of any given degree converge, for large number of vertices, to a constant times that number of vertices. The values of these constants depend on the degree and the distribution. However, even for simple cases—such as the number of leaves for points uniformly distributed in a unit square—their precise values are not known.[17]

### Empty regions

Empty regions for the Euclidean minimum spanning tree: For the red edge shown, these regions cannot contain any other vertices of the tree. White: the empty lens defining the relative neighborhood graph. Light blue: the diameter circle defining the Gabriel graph and forming an empty circle for the Delaunay triangulation. Dark blue: a 60°–120° rhombus that cannot overlap with the rhombi of other spanning tree edges.

For any edge ${\displaystyle uv}$ of any Euclidean minimum spanning tree, the lens (or vesica piscis) formed by intersecting the two circles with ${\displaystyle uv}$ as their radii cannot have any other given vertex ${\displaystyle w}$ in its interior. Put another way, if any tree has an edge ${\displaystyle uv}$ whose lens contains a third point ${\displaystyle w}$, then it is not of minimum length. For, by the geometry of the two circles, ${\displaystyle w}$ would be closer to both ${\displaystyle u}$ and ${\displaystyle v}$ than they are to each other. If edge ${\displaystyle uv}$ were removed from the tree, ${\displaystyle w}$ would remain connected to one of ${\displaystyle u}$ and ${\displaystyle v}$, but not the other. Replacing the removed edge ${\displaystyle uv}$ by ${\displaystyle uw}$ or ${\displaystyle vw}$ (whichever of these two edges reconnects ${\displaystyle w}$ to the vertex from which it was disconnected) would produce a shorter tree.[12]

For any edge ${\displaystyle uv}$ of any Euclidean minimum spanning tree, the rhombus with angles of 60° and 120°, having ${\displaystyle uv}$ as its long diagonal, is disjoint from the rhombi formed analogously by all other edges. Two edges sharing an endpoint cannot have overlapping rhombi, because that would imply a edge angle sharper than 60°, and two disjoint edges cannot have overlapping rhombi; if they did, the longer of the two edges could be replaced by a shorter edge among the same four vertices.[12]

### Supergraphs

Certain geometric graphs have definitions involving empty regions in point sets, from which it follows that they contain every edge that can be part of a Euclidean minimum spanning tree. These include:

• The relative neighborhood graph, which has an edge between any pair of points whenever the lens they define is empty.
• The Gabriel graph, which has an edge between any pair of points whenever the circle having the pair as a diameter is empty.
• The Delaunay triangulation, which has an edge between any pair of points whenever there exists an empty circle having the pair as a chord.
• The Urquhart graph, formed from the Delaunay triangulation by removing the longest edge of each triangle. For each remaining edge, the vertices of the Delaunay triangles that use that edge cannot lie within the empty lune of the relative neighborhood graph.

Because the empty-region criteria for these graphs are progressively weaker, these graphs form an ordered sequence of subgraphs. That is, using "⊆" to denote the subset relationship among their edges, these graphs have the relations:

Euclidean minimum spanning tree ⊆ relative neighborhood graph ⊆ Urquhart graph ⊆ Gabriel graph ⊆ Delaunay triangulation.[18][19]

Another graph guaranteed to contain the minimum spanning tree is the Yao graph, determined for points in the plane by dividing the plane around each point into six 60° wedges and connecting each point to the nearest neighbor in each wedge. The resulting graph contains the relative neighborhood graph, because two vertices with an empty lens must be the nearest neighbors to each other in their wedges. As with many of the other geometric graphs above, this definition can be generalized to higher dimensions, and (unlike the Delaunay triangulation) its generalizations always include a linear number of edges.[20][21]

### Total length

For ${\displaystyle n}$ points in the unit square (or any other fixed shape), the total length of the minimum spanning tree edges is ${\displaystyle O({\sqrt {n}})}$. Some sets of points, such as points evenly spaced in a ${\displaystyle {\sqrt {n}}\times {\sqrt {n}}}$ grid, attain this bound.[12] For points in a unit hypercube in ${\displaystyle d}$-dimensional space, the corresponding bound is ${\displaystyle O(n^{(d-1)/d})}$.[22] The same bound applies to the expected total length of the minimum spanning tree for ${\displaystyle n}$ points chosen uniformly and independently from a unit square or unit hypercube.[23] Returning to the unit square, the sum of squared edge lengths of the minimum spanning tree is ${\displaystyle O(1)}$. This bound follows from the observation that the edges have disjoint rhombi, with area proportional to the edge lengths squared. The ${\displaystyle O({\sqrt {n}})}$ bound on total length follows by application of the Cauchy–Schwarz inequality.[12]

Another interpretation of these results is that the average edge length for any set of points in a unit square is ${\displaystyle O(1/{\sqrt {n}})}$, at most proportional to the spacing of points in a regular grid; and that for random points in a unit square the average length is proportional to ${\displaystyle 1/{\sqrt {n}}}$. However, in the random case, with high probability the longest edge has length approximately

${\displaystyle {\sqrt {\frac {\log n}{\pi n}}},}$
longer than the average by a non-constant factor. With high probability, the longest edge forms a leaf of the spanning tree, and connects a point far from all the other points to its nearest neighbor. For large numbers of points, the distribution of the longest edge length around its expected value converges to a Laplace distribution.[24]

Any geometric spanner, a subgraph of a complete geometric graph whose shortest paths approximate the Euclidean distance, must have total edge length at least as large as the minimum spanning tree, and one of the standard quality measures for a geometric spanner is the ratio between its total length and of the minimum spanning tree for the same points. Several methods for constructing spanners, such as the greedy geometric spanner, achieve a constant bound for this ratio.[13] It has been conjectured that the Steiner ratio, the largest possible ratio between the total length of a minimum spanning tree and Steiner tree for the same set of points in the plane, is ${\displaystyle 2/{\sqrt {3}}\approx 1.1547}$, the ratio for three points in an equilateral triangle.[12]

### Subdivision

If every edge of a Euclidean minimum spanning tree is subdivided, by adding a new point at its midpoint, then the resulting tree is still a minimum spanning tree of the augmented point set. Repeating this subdivision process allows a Euclidean minimum spanning tree to be subdivided arbitrarily finely. However, subdividing only some of the edges, or subdividing the edges at points other than the midpoint, may produce a point set for which the subdivided tree is not the minimum spanning tree.[25]

## Computational complexity

For points in any dimension, the minimum spanning tree can be constructed in time ${\displaystyle O(n^{2})}$ by constructing a complete graph with an edge between every pair of points, weighted by Euclidean distance, and then applying a graph minimum spanning tree algorithm such as the Prim–Dijkstra–Jarník algorithm or Borůvka's algorithm on it. These algorithms can be made to take time ${\displaystyle O(n^{2})}$ on complete graphs, unlike another common choice, Kruskal's algorithm, which is slower because it involves sorting all distances.[13] For points in low-dimensional spaces, the problem may be solved more quickly, as detailed below.

Computing Euclidean distances involves a square root calculation. In any comparison of edge weights, comparing the squares of the Euclidean distances, instead of the distances themselves, yields the same ordering, and so does not change the rest of the tree's computation. This shortcut speeds up calculation and allows a minimum spanning tree for points with integer coordinates to be constructed using only integer arithmetic.[20]

### Two dimensions

A faster approach to finding the minimum spanning tree of planar points uses the property that it is a subgraph of the Delaunay triangulation:

1. Compute the Delaunay triangulation, which can be done in ${\displaystyle O(n\log n)}$ time. Because the Delaunay triangulation is a planar graph, it has at most ${\displaystyle 3n-6}$ edges.
2. Label each edge with its (squared) length.
3. Run a graph minimum spanning tree algorithm. Since there are ${\displaystyle O(n)}$ edges, this requires ${\displaystyle O(n\log n)}$ time using any of the standard minimum spanning tree algorithms.

The result is an algorithm taking ${\displaystyle O(n\log n)}$ time,[2] optimal in certain models of computation (see below).

If the input coordinates are integers and can be used as array indices, faster algorithms are possible: the Delaunay triangulation can be constructed by a randomized algorithm in ${\displaystyle O(n\log \log n)}$ expected time.[26] Additionally, since the Delaunay triangulation is a planar graph, its minimum spanning tree can be found in linear time by a variant of Borůvka's algorithm that removes all but the cheapest edge between each pair of components after each stage of the algorithm.[13][27] Therefore, the total expected time for this algorithm is ${\displaystyle O(n\log \log n)}$.[26] In the other direction, the Delaunay triangulation can be constructed from the minimum spanning tree in the near-linear time bound ${\displaystyle O(n\log ^{*}n)}$, where ${\displaystyle \log ^{*}}$ denotes the iterated logarithm.[28]

### Higher dimensions

The problem can also be generalized to ${\displaystyle n}$ points in the ${\displaystyle d}$-dimensional space ${\displaystyle \mathbb {R} ^{d}}$. In higher dimensions, the connectivity determined by the Delaunay triangulation (which, likewise, partitions the convex hull into ${\displaystyle d}$-dimensional simplices) contains the minimum spanning tree; however, the triangulation might contain the complete graph.[4] Therefore, finding the Euclidean minimum spanning tree as a spanning tree of the complete graph or as a spanning tree of the Delaunay triangulation both take ${\displaystyle O(dn^{2})}$ time. For three dimensions the minimum spanning tree can be found in time ${\displaystyle O{\bigl (}(n\log n)^{4/3}{\bigr )}}$, and in any greater dimension, in time

${\displaystyle O\left(n^{2-{\frac {2}{\lceil d/2\rceil +1}}+\varepsilon }\right)}$
for any ${\displaystyle \varepsilon >0}$—faster than the quadratic time bound for the complete graph and Delaunay triangulation algorithms.[4]

The optimal time complexity for higher-dimensional minimum spanning trees remains unknown,[29] but is closely related to the complexity of computing bichromatic closest pairs. In the bichromatic closest pair problem, the input is a set of points, given two different colors (say, red and blue). The output is a pair of a red point and a blue point with the minimum possible distance. This pair always forms one of the edges in the minimum spanning tree. Therefore, the bichromatic closest pair problem can be solved in the amount of time that it takes to construct a minimum spanning tree and scan its edges for the shortest red–blue edge. Conversely, for any red–blue coloring of any subset of a given set of points, the bichromatic closest pair produces one edge of the minimum spanning tree of the subset. By carefully choosing a sequence of colorings of subsets, and finding the bichromatic closest pair of each subproblem, the minimum spanning tree may be found in time proportional to the optimal time for finding bichromatic closest pairs for the same number of points, whatever that optimal time turns out to be.[4][11]

For uniformly random point sets in any bounded dimension, the Yao graph[20] or Delaunay triangulation have linear expected numbers of edges, are guaranteed to contain the minimum spanning tree, and can be constructed in linear expected time.[21][6][30] From these graphs, the minimum spanning tree itself may be constructed in linear time, by using a randomized linear time algorithm for graph minimum spanning trees.[31] However, the poor performance of these methods on inputs coming from clustered data has led algorithm engineering researchers to develop methods with a somewhat slower ${\displaystyle O(n\log n)}$ time bound, for random inputs or inputs whose distances and clustering resemble those of random data, while exhibiting better performance on real-world data.[8][32][5]

A well-separated pair decomposition is a family of pairs of subsets of the given points, so that every pair of points belong to one of these pairs of subsets, and so that all pairs of points coming from the same pair of subsets have approximately the same length. It is possible to find a well-separated pair decomposition with a linear number of subsets, and a representative pair of points for each subset, in time ${\displaystyle O(n\log n)}$. The minimum spanning tree of the graph formed by these representative pairs is then an approximation to the minimum spanning tree. Using these ideas, a ${\displaystyle (1+\varepsilon )}$-approximation to the minimum spanning tree may be found in ${\displaystyle O(n\log n)}$ time, for constant ${\displaystyle \varepsilon }$. More precisely, by choosing each representative pair to approximate the closest pair in its equivalence class, and carefully varying the quality of this approximation for different pairs, the dependence on ${\displaystyle \varepsilon }$ in the time bound can be given as ${\displaystyle O(n\log n+(\varepsilon ^{-2}\log ^{2}{\tfrac {1}{\varepsilon }})n),}$ for any fixed dimension.[33]

### Dynamic and kinetic

The Euclidean minimum spanning tree has been generalized in many different ways to systems of moving or changing points:

• If a set of points undergoes a sequence of dynamic insertions or deletions of points, each of these updates induces a bounded amount of change to the minimum spanning tree of the points. When the update sequence is known in advance, for points in the plane, the change after each insertion or deletion can be found in time ${\displaystyle O(\log ^{2}n)}$ per insertion or deletion.[34] When the updates must be handled in an online manner, a slower (but still poly-logarithmic) ${\displaystyle O(\log ^{10}n)}$ time bound is known.[35] For higher-dimensional versions of the problem the time per update is slower, but still sublinear.[36]
• For ${\displaystyle n}$ points moving linearly with constant speed, or with more general algebraic motions, the minimum spanning tree will change by a sequence of swaps, in which one edge is removed and another replaces it at a point in time where both have equal length.[37] For linear motions, the number of changes is at most slightly larger than ${\displaystyle n^{25/9}}$.[38] For more general algebraic motions, there is a near-cubic upper bound on the number of swaps, based on the theory of Davenport–Schinzel sequences.[39]
• The minimum moving spanning tree problem again concerns points moving linearly with constant speed, over an interval of time, and seeks a single tree that minimizes the maximum sum of weights occurring at any instant during this interval. It is NP-hard to compute exactly, but can be approximated to within a factor of two in polynomial time.[40]
• The kinetic Euclidean minimum spanning tree problem asks for a kinetic data structure that can maintain the minimum spanning tree as its points undergo both continuous motions and insertions and deletions. Several papers have studied such structures,[41][42][43][44][45] and a kinetic structure for algebraically moving points with near-cubic total time, nearly matching the bound on the number of swaps, is known.[44]

### Lower bound

An asymptotic lower bound of ${\displaystyle \Omega (n\log n)}$ of the Euclidean minimum spanning tree problem can be established in restricted models of computation. These include the algebraic decision tree and algebraic computation tree models, in which the algorithm has access to the input points only through certain restricted primitives that perform simple algebraic computations on their coordinates. In these models, the closest pair of points problem requires ${\displaystyle \Omega (n\log n)}$ time, but the closest pair is necessarily an edge of the minimum spanning tree, so the minimum spanning tree also requires this much time. Therefore, algorithms for constructing the planar minimum spanning tree in time ${\displaystyle O(n\log n)}$ within this model, for instance by using the Delaunay triangulation, are optimal.[46] However, these lower bounds do not apply to models of computation with integer point coordinates, in which bitwise operations and table indexing operations on those coordinates are permitted. In these models, faster algorithms are possible, as described above.[26]

## Applications

An obvious application of Euclidean minimum spanning trees is to find the cheapest network of wires or pipes to connect a set of places, assuming the links cost a fixed amount per unit length. The first publications on minimum spanning trees more generally concerned a geographic version of the problem, involving the design of an electrical grid for southern Moravia,[47] and an application to minimizing wire lengths in circuits was described in 1957 by Loberman and Weinberger.[48]

Minimum spanning trees are closely related to single-linkage clustering, one of several methods for hierarchical clustering. The edges of a minimum spanning tree, sorted by their length, give the order in which to merge clusters into larger clusters in this clustering method. Once these edges have been found, by any algorithm, they may be used to construct the single-linkage clustering in time ${\displaystyle O(n\log n)}$.[1] Although the long thin cluster shapes produced by single-linkage clustering can be a bad fit for certain types of data, such as mixtures of Gaussian distributions, it can be a good choice in applications where the clusters themselves are expected to have long thin shapes, such as in modeling the dark matter halos of galaxies.[5] In geographic information science, several researcher groups have used minimum spanning trees of the centroids of buildings to identify meaningful clusters of buildings, for instance by removing edges identified in some other way as inconsistent.[49]

Minimum spanning trees have also been used to infer the shape of curves in the plane, given points sampled along the curve. For a smooth curve, sampled more finely than its local feature size, the minimum spanning tree will form a path connecting consecutive points along the curve. More generally, similar methods can recognize curves drawn in a dotted or dashed style rather than as a single connected set. Applications of this curve-finding technique include particle physics, in automatically identifying the tracks left by particles in a bubble chamber.[50] More sophisticated versions of this idea can find curves from a cloud of noisy sample points that roughly follows the curve outline, by using the topology of the spanning tree to guide a moving least squares method.[51]

Another application of minimum spanning trees is a constant-factor approximation algorithm for the Euclidean traveling salesman problem, the problem of finding the shortest polygonalization of a point set. Walking around the boundary of the minimum spanning tree can approximate the optimal traveling salesman tour within a factor of two of the optimal length.[2] However, more accurate polynomial-time approximation schemes are known for this problem.[52] In wireless ad hoc networks, broadcasting messages along paths in a minimum spanning tree can be an accurate approximation to the minimum-energy broadcast routing, which is, again, hard to compute exactly.[53][54][55][56]

## Realization

The realization problem for Euclidean minimum spanning trees takes an abstract tree as input and seeks a geometric location for each vertex of the tree (in a space of some fixed dimension), such that the given tree equals the minimum spanning tree of those points. Not every abstract tree has such a realization; for instance, the tree must obey the kissing number bound on the degree of each vertex. Additional restrictions exist; for instance, it is not possible for a planar minimum spanning tree to have a degree-six vertex adjacent to a vertex of degree five or six.[7] Determining whether a two-dimensional realization exists is NP-hard. However, the proof of hardness depends on the fact that degree-six vertices in a tree have a very restricted set of realizations: the neighbors of such a vertex must be placed on the vertices of a regular hexagon centered at that vertex.[57] Indeed, for trees of maximum degree five, a planar realization always exists.[7] Similarly, for trees of maximum degree ten, a three-dimensional realization always exists.[10] For these realizations, some trees may require edges of exponential length and bounding boxes of exponential area relative to the length of their shortest edge.[58] Trees of maximum degree four have smaller planar realizations, with polynomially bounded edge lengths and bounding boxes.[9]

## References

1. ^ a b Gower, J. C.; Ross, G. J. S. (1969), "Minimum spanning trees and single linkage cluster analysis", Applied Statistics, 18 (1): 54–61, doi:10.2307/2346439, JSTOR 2346439, MR 0242315
2. ^ a b c d Shamos, Michael Ian; Hoey, Dan (1975), "Closest-point problems", 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975, IEEE Computer Society, pp. 151–162, doi:10.1109/SFCS.1975.8, MR 0426498, S2CID 40615455
3. ^ Bose, Prosenjit; Devroye, Luc; Evans, William; Kirkpatrick, David (2006), "On the spanning ratio of Gabriel graphs and β-skeletons", SIAM Journal on Discrete Mathematics, 20 (2): 412–427, doi:10.1137/S0895480197318088, MR 2257270
4. ^ a b c d Agarwal, P. K.; Edelsbrunner, H.; Schwarzkopf, O.; Welzl, E. (1991), "Euclidean minimum spanning trees and bichromatic closest pairs", Discrete & Computational Geometry, Springer, 6 (1): 407–422, doi:10.1007/BF02574698, MR 1115099
5. ^ a b c March, William B.; Ram, Parikshit; Gray, Alexander G. (2010), "Fast Euclidean minimum spanning tree: algorithm, analysis, and applications", in Rao, Bharat; Krishnapuram, Balaji; Tomkins, Andrew; Yang, Qiang (eds.), Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, July 25-28, 2010, pp. 603–612, doi:10.1145/1835804.1835882, S2CID 186025
6. ^ a b Clarkson, Kenneth L. (1989), "An algorithm for geometric minimum spanning trees requiring nearly linear expected time", Algorithmica, 4 (1–4): 461–469, doi:10.1007/BF01553902, MR 1019387, S2CID 22176641
7. ^ a b c d Monma, Clyde; Suri, Subhash (1992), "Transitions in geometric minimum spanning trees", Discrete & Computational Geometry, 8 (3): 265–293, doi:10.1007/BF02293049, MR 1174358, S2CID 30101649
8. ^ a b Narasimhan, Giri; Zachariasen, Martin; Zhu, Jianlin (2000), "Experiments with computing geometric minimum spanning trees", Proceedings of the 2nd Workshop on Algorithm Engineering and Experiments, pp. 183–196
9. ^ a b Frati, Fabrizio; Kaufmann, Michael (2011), "Polynomial area bounds for MST embeddings of trees", Computational Geometry: Theory and Applications, 44 (9): 529–543, doi:10.1016/j.comgeo.2011.05.005, MR 2819643, S2CID 5634139
10. ^ a b King, James A. (2006), "Realization of degree 10 minimum spanning trees in 3-space" (PDF), Proceedings of the 18th Annual Canadian Conference on Computational Geometry, CCCG 2006, August 14-16, 2006, Queen's University, Ontario, Canada, pp. 39–42
11. ^ a b Krznaric, Drago; Levcopoulos, Christos; Nilsson, Bengt J. (1999), "Minimum spanning trees in ${\displaystyle d}$ dimensions", Nordic Journal of Computing, 6 (4): 446–461, MR 1736451. This version of this paper is not available online; instead, see the 1997 conference version of the same paper, doi:10.1007/3-540-63397-9_26.
12. Gilbert, E. N.; Pollak, H. O. (1968), "Steiner minimal trees", SIAM Journal on Applied Mathematics, 16 (1): 1–29, doi:10.1137/0116001, JSTOR 2099400, MR 0223269
13. ^ a b c d Eppstein, David (1999), "Spanning trees and spanners" (PDF), in Sack, J.-R.; Urrutia, J. (eds.), Handbook of Computational Geometry, Elsevier, pp. 425–461, MR 1746681
14. ^ Georgakopoulos, George; Papadimitriou, Christos H. (1987), "The 1-Steiner tree problem", Journal of Algorithms, 8 (1): 122–130, doi:10.1016/0196-6774(87)90032-0, MR 0875330
15. ^ a b Robins, G.; Salowe, J. S. (1995), "Low-degree minimum spanning trees", Discrete & Computational Geometry, 14 (2): 151–165, doi:10.1007/BF02570700, MR 1331924, S2CID 16040977
16. ^ Pfender, Florian; Ziegler, Günter M. (September 2004), "Kissing numbers, sphere packings, and some unexpected proofs" (PDF), Notices of the American Mathematical Society: 873–883
17. ^ Steele, J. Michael; Shepp, Lawrence A.; Eddy, William F. (1987), "On the number of leaves of a Euclidean minimal spanning tree", Journal of Applied Probability, 24 (4): 809–826, doi:10.2307/3214207, JSTOR 3214207, MR 0913823, S2CID 29026025
18. ^ Preparata, Franco P.; Shamos, Michael Ian (1985), Computational Geometry: An Introduction, Texts and Monographs in Computer Science, Springer-Verlag, New York, p. 263, doi:10.1007/978-1-4612-1098-6, ISBN 0-387-96131-3, MR 0805539, S2CID 206656565
19. ^ Toussaint, G. T. (1980), "Comment: Algorithms for computing relative neighborhood graph", Electronics Letters, 16 (22): 860, Bibcode:1980ElL....16..860T, doi:10.1049/el:19800611; reply by Urquhart, pp. 860–861
20. ^ a b c Yao, Andrew Chi Chih (1982), "On constructing minimum spanning trees in k-dimensional spaces and related problems", SIAM Journal on Computing, 11 (4): 721–736, doi:10.1137/0211059, MR 0677663
21. ^ a b Bentley, Jon Louis; Weide, Bruce W.; Yao, Andrew C. (1980), "Optimal expected-time algorithms for closest point problems", ACM Transactions on Mathematical Software, 6 (4): 563–580, doi:10.1145/355921.355927, MR 0599977, S2CID 17238717
22. ^
23. ^ Steele, J. Michael (1988), "Growth rates of Euclidean minimal spanning trees with power weighted edges", Annals of Probability, 16 (4): 1767–1787, doi:10.1214/aop/1176991596, JSTOR 2243991, MR 0958215
24. ^ Penrose, Mathew D. (1997), "The longest edge of the random minimal spanning tree", The Annals of Applied Probability, 7 (2): 340–361, doi:10.1214/aoap/1034625335, MR 1442317
25. ^ Boyce, W. M.; Garey, M. R.; Johnson, D. S. (1978), "A note on bisecting minimum spanning trees", Networks, 8 (3): 187–192, doi:10.1002/net.3230080302, MR 0491324
26. ^ a b c Buchin, Kevin; Mulzer, Wolfgang (2011), "Delaunay triangulations in O(sort(n)) time and more", Journal of the ACM, 58 (2): A6:1–A6:27, doi:10.1145/1944345.1944347, MR 2786587, S2CID 11316974
27. ^ Mareš, Martin (2004), "Two linear time algorithms for MST on minor closed graph classes" (PDF), Archivum Mathematicum, 40 (3): 315–320, MR 2107027
28. ^ Devillers, Olivier (1992), "Randomization yields simple O(n log* n) algorithms for difficult Ω(n) problems" (PDF), International Journal of Computational Geometry & Applications, 2 (1): 97–111, doi:10.1142/S021819599200007X, MR 1159844, S2CID 60203
29. ^ O'Rourke, J.; Demaine, E. (2001–2002), "Problem 5: Euclidean Minimum Spanning Tree", The Open Problems Project, Smith College
30. ^ Dwyer, Rex A. (1991), "Higher-dimensional Voronoi diagrams in linear expected time", Discrete & Computational Geometry, 6 (4): 343–367, doi:10.1007/BF02574694, MR 1098813
31. ^ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995), "A randomized linear-time algorithm to find minimum spanning trees", Journal of the ACM, 42 (2): 321–328, doi:10.1145/201019.201022, MR 1409738, S2CID 832583
32. ^ Chatterjee, S.; Connor, M.; Kumar, P. (2010), "Geometric minimum spanning trees with GeoFilterKruskal", in Festa, Paola (ed.), Experimental Algorithms: 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010, Proceedings, Lecture Notes in Computer Science, vol. 6049, Springer-Verlag, pp. 486–500, doi:10.1007/978-3-642-13193-6_41
33. ^ Arya, Sunil; Mount, David M. (2016), "A fast and simple algorithm for computing approximate Euclidean minimum spanning trees", in Krauthgamer, Robert (ed.), Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pp. 1220–1233, doi:10.1137/1.9781611974331.ch85, MR 3478461
34. ^ Eppstein, David (1994), "Offline algorithms for dynamic minimum spanning tree problems", Journal of Algorithms, 17 (2): 237–250, doi:10.1006/jagm.1994.1033, MR 1291541
35. ^ Chan, Timothy M. (2010), "A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries", Journal of the ACM, 57 (3): Article 16, doi:10.1145/1706591.1706596, MR 2665885, S2CID 47454142
36. ^ Eppstein, David (1995), "Dynamic Euclidean minimum spanning trees and extrema of binary functions", Discrete & Computational Geometry, 13 (1): 111–122, doi:10.1007/BF02574030, MR 1300511, S2CID 7339165
37. ^ Katoh, N.; Tokuyama, T.; Iwano, K. (1995), "On minimum and maximum spanning trees of linearly moving points", Discrete & Computational Geometry, 13 (2): 161–176, doi:10.1007/BF02574035, MR 1314960
38. ^ Chan, Timothy M. (2003), "On levels in arrangements of curves", Discrete & Computational Geometry, 29 (3): 375–393, doi:10.1007/s00454-002-2840-2, MR 1961005, S2CID 18966889
39. ^ Rahmati, Zahed; Zarei, Alireza (2010), "Combinatorial changes of Euclidean minimum spanning tree of moving points in the plane" (PDF), Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, Winnipeg, Manitoba, Canada, August 9-11, 2010, pp. 43–45
40. ^ Akitaya, Hugo A.; Biniaz, Ahmad; Bose, Prosenjit; De Carufel, Jean-Lou; Maheshwari, Anil; da Silveira, Luís Fernando Schultz Xavier; Smid, Michiel (2021), "The minimum moving spanning tree problem", in Lubiw, Anna; Salavatipour, Mohammad R. (eds.), Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings, Lecture Notes in Computer Science, vol. 12808, Springer, pp. 15–28, doi:10.1007/978-3-030-83508-8_2, S2CID 234599877
41. ^ Basch, Julien; Guibas, Leonidas J.; Zhang, Li (1997), "Proximity problems on moving points", in Boissonnat, Jean-Daniel (ed.), Proceedings of the Thirteenth Annual Symposium on Computational Geometry, Nice, France, June 4–6, 1997, Association for Computing Machinery, pp. 344–351, doi:10.1145/262839.262998, S2CID 15556637
42. ^ Agarwal, Pankaj K.; Eppstein, David; Guibas, Leonidas J.; Henzinger, Monika Rauch (1998), "Parametric and Kinetic Minimum Spanning Trees", 39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8–11, 1998, Palo Alto, California, USA (PDF), IEEE Computer Society, pp. 596–605, doi:10.1109/SFCS.1998.743510, S2CID 2559456
43. ^ Rahmati, Zahed; Zarei, Alireza (2012), "Kinetic Euclidean minimum spanning tree in the plane", Journal of Discrete Algorithms, 16: 2–11, doi:10.1016/j.jda.2012.04.009, MR 2960341
44. ^ a b Rahmati, Zahed; Abam, Mohammad Ali; King, Valerie; Whitesides, Sue; Zarei, Alireza (2015), "A simple, faster method for kinetic proximity problems", Computational Geometry: Theory & Applications, 48 (4): 342–359, doi:10.1016/j.comgeo.2014.12.002, MR 3296072, S2CID 18971251
45. ^ Meulemans, Wouter; Speckmann, Bettina; Verbeek, Kevin; Wulms, Jules (2018), "A framework for algorithm stability and its application to kinetic Euclidean MSTs", in Bender, Michael A.; Farach-Colton, Martin; Mosteiro, Miguel A. (eds.), LATIN 2018: Theoretical Informatics – 13th Latin American Symposium, Buenos Aires, Argentina, April 16–19, 2018, Proceedings, Lecture Notes in Computer Science, vol. 10807, Springer, pp. 805–819, doi:10.1007/978-3-319-77404-6_58, S2CID 4709616
46. ^ Yao, Andrew Chi-Chih (1991), "Lower bounds for algebraic computation trees with integer inputs", SIAM Journal on Computing, 20 (4): 655–668, doi:10.1137/0220041, MR 1105929
47. ^ Graham, R. L.; Hell, Pavol (1985), "On the history of the minimum spanning tree problem", IEEE Annals of the History of Computing, 7 (1): 43–57, doi:10.1109/mahc.1985.10011, MR 0783327, S2CID 10555375
48. ^ Loberman, H.; Weinberger, A. (October 1957), "Formal procedures for connecting terminals with a minimum total wire length", Journal of the ACM, 4 (4): 428–437, doi:10.1145/320893.320896, S2CID 7320964
49. ^ Wu, Bin; Yu, Bailang; Wu, Qiusheng; Chen, Zuoqi; Yao, Shenjun; Huang, Yan; Wu, Jianping (October 2017), "An extended minimum spanning tree method for characterizing local urban patterns", International Journal of Geographical Information Science, 32 (3): 450–475, doi:10.1080/13658816.2017.1384830, S2CID 46772272
50. ^ Zahn, C. T. (1973), "Using the minimum spanning tree to recognize dotted and dashed curves", 1st International Computing Symposium, Davos, Switzerland, 4–7 September 1973
51. ^ Lee, In-Kwon (2000), "Curve reconstruction from unorganized points", Computer Aided Geometric Design, 17 (2): 161–177, doi:10.1016/S0167-8396(99)00044-8, MR 1733203
52. ^ Bartal, Yair; Gottlieb, Lee-Ad (2013), "A linear time approximation scheme for Euclidean TSP", 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pp. 698–706, doi:10.1109/FOCS.2013.80, MR 3246273, S2CID 17514182
53. ^ Wan, P.-J.; Călinescu, G.; Li, X.-Y.; Frieder, O. (2002), "Minimum-energy broadcasting in static ad hoc wireless networks", Wireless Networks, 8 (6): 607–617, doi:10.1023/a:1020381720601, S2CID 1297518
54. ^ Clementi, Andrea E. F.; Huiban, Gurvan; Rossi, Gianluca; Verhoeven, Yann C.; Penna, Paolo (2003), "On the approximation ratio of the MST-based heuristic for the energy-efficient broadcast problem in static ad-hoc radio networks", 17th International Parallel and Distributed Processing Symposium (IPDPS 2003), 22-26 April 2003, Nice, France, Proceedings, IEEE Computer Society, p. 222, doi:10.1109/IPDPS.2003.1213407, S2CID 17863487
55. ^ Flammini, Michele; Klasing, Ralf; Navarra, Alfredo; Perennes, Stephane (2007), "Improved approximation results for the minimum energy broadcasting problem", Algorithmica, 49 (4): 318–336, doi:10.1007/s00453-007-9077-7, MR 2358524, S2CID 11982404
56. ^ Ambühl, Christoph (2005), "An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks", in Caires, Luís; Italiano, Giuseppe F.; Monteiro, Luís; Palamidessi, Catuscia; Yung, Moti (eds.), Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3580, Springer, pp. 1139–1150, doi:10.1007/11523468_92
57. ^ Eades, Peter; Whitesides, Sue (1996), "The realization problem for Euclidean minimum spanning trees is NP-hard", Algorithmica, 16 (1): 60–82, doi:10.1007/s004539900037, MR 1394494
58. ^ Angelini, Patrizio; Bruckdorfer, Till; Chiesa, Marco; Frati, Fabrizio; Kaufmann, Michael; Squarcella, Claudio (2014), "On the area requirements of Euclidean minimum spanning trees", Computational Geometry: Theory and Applications, 47 (2, part B): 200–213, doi:10.1016/j.comgeo.2012.10.011, MR 3123788


text:
### Roll These Dice

Roll two red dice and a green dice. Add the two numbers on the red dice and take away the number on the green. What are all the different possibilities that could come up?

### Bipin's Choice

Bipin is in a game show and he has picked a red ball out of 10 balls. He wins a large sum of money, but can you use the information to decided what he should do next?

### Trick or Treat

Mrs. Smith had emptied packets of chocolate-covered mice, plastic frogs and gummi-worms into a cauldron for treats. What treat is Trixie most likely to pick out?

# A Bit of a Dicey Problem

##### Stage: 2 Challenge Level:
William from Churchers College Junior School sent in his good explanations.

$1$a You can roll numbers between $2$ and $12$ with two six-sided dice
b $7$: Because you can roll combinations which use all the numbers on the dice.
$1-6$, $6-1$, $5-2$, $2-5$, $4-3$, $3-4$

$6$ combinations give $7$.
There are $36$ possible combinations when you threw two six-sided dice SO $6$ /$36 \times 100 = 16.67$ % chance of rolling $7$ with two six-sided dice.

$2$a With two ten-sided dice you can roll numbers between $2$ and $20$.
b  $11$; because there are ten combinations which give $11$ which use all the numbers on the dice
There are are $100$ possibilities when you roll two ten-sided dice.
So $10$/$100 \times 100 = 10$ % chance of rolling $11$ with $2$,  $10$ sided dice.

From Oscar at CCJS (which I think is Cheltenham College Junior School - but forgive me if I'm wrong!) also worked on this and sent in the following;

I wrote down every possible throw I could get using a black and white six-faced dice - it came to $36$ possibilites.
I counted how many of each total number I could get and found that the commonest total number to get was $7$
Two six-faced dice gave me $36$ possibilities. That is $6$ squared or $6 \times 6$.
The two six-faced dice had $7$ as the commonest number that we could get - that is, one greater than the number of sides on each dice.

Finally Tom from Fen Ditton C.P. School wrote to tell us what he already knew or what he found out by doing the activity:

$6$ numbered  dice: the most likely number is $7$ because is has got the most combinations.
$10$ numbered dice: $11$ is the most likely  because it has the most combinations.
The formula for this problem is:n $+1$     n= no. of  sides on the die.

Well done all of you, three excellent solutions sent in, keep up the good work!

format: plain


text:
This content will become publicly available on April 1, 2023

First Census of Gas-phase Metallicity Gradients of Star-forming Galaxies in Overdense Environments at Cosmic Noon
Abstract We report the first spatially resolved measurements of gas-phase metallicity radial gradients in star-forming galaxies in overdense environments at z ≳ 2. The spectroscopic data are acquired by the MAMMOTH-Grism survey, a Hubble Space Telescope (HST) cycle 28 medium program. This program is obtaining 45 orbits of WFC3/IR grism spectroscopy in the density peak regions of three massive galaxy protoclusters (BOSS 1244, BOSS 1542, and BOSS 1441) at z = 2–3. Our sample in the BOSS 1244 field consists of 20 galaxies with stellar mass ranging from 10 9.0 to 10 10.3 M ⊙ , star formation rate (SFR) from 10 to 240 M ⊙ yr −1 , and global gas-phase metallicity ( 12 + log ( O / H ) ) from 8.2 to 8.6. At 1 σ confidence level, 2/20 galaxies in our sample show positive (inverted) gradients—the relative abundance of oxygen increasing with galactocentric radius, opposite the usual trend. Furthermore, 1/20 shows negative gradients, and 17/20 are consistent with flat gradients. This high fraction of flat/inverted gradients is uncommon in simulations and previous observations conducted in blank fields at similar redshifts. To understand this, we investigate the correlations among various observed properties of our sample galaxies. more »
Authors:
; ; ; ; ; ; ; ; ; ;
Award ID(s):
Publication Date:
NSF-PAR ID:
10381315
Journal Name:
The Astrophysical Journal Letters
Volume:
929
Issue:
1
Page Range or eLocation-ID:
L8
ISSN:
2041-8205
3. ABSTRACT We measure the rate of environmentally driven star formation quenching in galaxies at z ∼ 1, using eleven massive ($M\approx 2\times 10^{14}\, \mathrm{M}_\odot$) galaxy clusters spanning a redshift range 1.0 < z < 1.4 from the GOGREEN sample. We identify three different types of transition galaxies: ‘green valley’ (GV) galaxies identified from their rest-frame (NUV − V) and (V − J) colours; ‘blue quiescent’ (BQ) galaxies, found at the blue end of the quiescent sequence in (U − V) and (V − J) colour; and spectroscopic post-starburst (PSB) galaxies. We measure the abundance of these galaxies as a function of stellar mass and environment. For high-stellar mass galaxies (log M/M⊙ > 10.5) we do not find any significant excess of transition galaxies in clusters, relative to a comparison field sample at the same redshift. It is likely that such galaxies were quenched prior to their accretion in the cluster, in group, filament, or protocluster environments. For lower stellar mass galaxies (9.5 < log M/M⊙ < 10.5) there is a small but significant excess of transition galaxies in clusters, accounting for an additional ∼5–10 per cent of the population compared with the field. We show that our data are consistent with a scenario inmore »
4. ABSTRACT We present a detailed study of two partial Lyman limit systems (pLLSs) of neutral hydrogen column density $N_\mathrm{H\, I}\approx (1-3)\times 10^{16}\, \mathrm{cm}^{-2}$ discovered at $z$ = 0.5 in the Cosmic Ultraviolet Baryon Survey (CUBS). Available far-ultraviolet spectra from the Hubble Space Telescope Cosmic Origins Spectrograph and optical echelle spectra from MIKE on the Magellan Telescopes enable a comprehensive ionization analysis of diffuse circumgalactic gas based on resolved kinematics and abundance ratios of atomic species spanning five different ionization stages. These data provide unambiguous evidence of kinematically aligned multiphase gas that masquerades as a single-phase structure and can only be resolved by simultaneous accounting of the full range of observed ionic species. Both systems are resolved into multiple components with inferred α-element abundance varying from [α/H] ≈−0.8 to near solar and densities spanning over two decades from log nH/cm−3 ≈ −2.2 to <−4.3. Available deep galaxy survey data from the CUBS program taken with VLT/MUSE, Magellan/LDSS3-C and Magellan/IMACS reveal that the $z$ = 0.47 system is located 55 kpc from a star-forming galaxy with prominent Balmer absorption of stellar mass ${{M_{\rm star}}}\approx 2\times 10^{10}\, {{M_{\odot}}}$, while the $z$ = 0.54 system resides in an overdense environment of 11 galaxies within 750 kpc in projected distance, withmore »


text:
## Stream: new members

### Topic: Proving complexity bounds

#### Meyer Zinn (Nov 25 2020 at 04:22):

I have a simple proof for an introductory computer science problem, which is simply showing that f(n)=n^2 is little-oh of g(n)=n^3 (since the limit as n tends to infinity of f(n)/g(n) is zero). However, I'm having trouble understanding how filters (and limits generally) work in Lean.

So far, I think I've been able to state the problem as

noncomputable def f : ℕ → ℝ := λ n, n ^ (2:ℤ)
noncomputable def g : ℕ → ℝ := λ n, n ^ (3:ℤ)
example : is_o f g filter.at_top := by sorry

(if I understand how asymptotics work. I chose to use integer exponents to be able to use fpow, but I don't know if that was the right move). I've also been able to do some manipulations to show that, when n \ne 0, f(n)/g(n)=1/(↑n) (for f g: nat -> real). How do I tie these together to show that the limit of 1/x tends to zero, and that implies little oh?

#### Floris van Doorn (Nov 25 2020 at 04:49):

The result docs#tendsto.inv_tendsto_zero (and the surrounding results) will be useful for this

#### Floris van Doorn (Nov 25 2020 at 04:50):

Oh, didn't mean that one. It is this result: docs#tendsto_inv_at_top_zero

#### Meyer Zinn (Nov 25 2020 at 05:07):

Floris van Doorn said:

Oh, didn't mean that one. It is this result: docs#tendsto_inv_at_top_zero

I'll take a look, thanks for the pointer!

#### Meyer Zinn (Nov 25 2020 at 05:19):

I guess now I'm a little confused by how to prove that the limit of f(n)/g(n) is the same as the limit of n^(-1). I shouldn't need to consider what actually happens at n=0 since that's the entire point of a limit, but the following strategy does not work to show equivalence:

have f_div_g_eq_x_inv : ∀ n, f n / g n = 1 / n := begin
intro n,
rw [f, g],
simp,
rw div_eq_mul_inv,
rw ← inv_fpow,
rw ← fpow_neg_one,
rw ← fpow_mul,
have neg_three : (-1 : ℤ) * 3 = -3 := by ring,
rw neg_three,
rw ← fpow_add,
have two_minus_three : (2 : ℤ) + (-3) = -1 := by ring,
rw two_minus_three,
-- need to prove \u n \ne 0
end,

I could amend the lemma to be \forall (n \ne 0) (or similar), but I return to the issue of not knowing how to interface with the limit definition.

#### Floris van Doorn (Nov 25 2020 at 05:50):

• About not knowing the interface: one way is to search for theorems (such as via https://leanprover-community.github.io/mathlib_docs/find/tendsto_congr) using our #naming conventions and then browsing results near the ones that look useful.
• You should be able to use prove the equality for all n, since division by 0 is defined to be 0. You could start the proof with by_cases hn : n = 0 and simp [hn] can simplify the fractions away in the case that n = 0.
• There should also be a congruence lemma for tendsto that allows you to only show the equality for "sufficiently large" n. I couldn't find such a result myself, though, so maybe it doesn't exist yet.

#### Anatole Dedecker (Nov 25 2020 at 06:58):

It should be docs#filter.tendsto_congr'

#### Anatole Dedecker (Nov 25 2020 at 08:14):

Oh and you might be interested by a result I proved in #4979 : https://github.com/leanprover-community/mathlib/pull/4979/files#diff-7adbc7098d121dfb6c1742ffe2994f62b43d80d894716e85a8e9260d670d5d7cR45

Last updated: May 13 2021 at 22:15 UTC


text:
## Maillard Sampling: Boltzmann Exploration Done Optimally

### Jie Bian · Kwang-Sung Jun

[ Abstract ]
Tue 29 Mar 1 a.m. PDT — 2:30 a.m. PDT

Abstract: The PhD thesis of Maillard (2013) presents a rather obscure algorithm for the $K$-armed bandit problem. This less-known algorithm, which we call Maillard sampling (MS), computes the probability of choosing each arm in a \textit{closed form}, which is not true for Thompson sampling, a widely-adopted bandit algorithm in the industry. This means that the bandit-logged data from running MS can be readily used for counterfactual evaluation, unlike Thompson sampling. Motivated by such merit, we revisit MS and perform an improved analysis to show that it achieves both the asymptotical optimality and $\sqrt{KT\log{T}}$ minimax regret bound where $T$ is the time horizon, which matches the known bounds for asymptotically optimal UCB. %'s performance. We then propose a variant of MS called MS$^+$ that improves its minimax bound to $\sqrt{KT\log{K}}$. MS$^+$ can also be tuned to be aggressive (i.e., less exploration) without losing the asymptotic optimality, a unique feature unavailable from existing bandit algorithms. Our numerical evaluation shows the effectiveness of MS$^+$.

Chat is not available.


text:
# The cost price of 30 pens is the same as the selling price of 27 pens. What is the percentage of profit or loss?

1. 10% profit
2. 11.11% loss
3. 10% loss
4. 11.11% profit
5. None of these

Option 4 : 11.11% profit
Free
Making of Constitution I
61123
15 Questions 15 Marks 9 Mins

## Detailed Solution

Given:

The selling price of 27 pens = cost price of 30 pens

Formula used:

Profit % = (selling price - cost price)/(cost price) × 100

Calculations:

Let the cost price of 1 pen be a

Cost price of 30 pens = 30a

According to the question

⇒ 27 × SP = 30a

⇒ SP = (10/9)a

Substituting the values in the formula

Profit% $$= \frac{{(10/9)a - a}}{a} × 100\% = \frac{{(1/9)a}}{a} × 100\%$$

Profit% = 1/9 × 100 = 11.11%

∴ The profit % will be 11.11%

Shortcut Trick

Short Trick

Cost price of 27 pens = 27a

Selling price of 27 pens = Cost price of 30 pens = 30a

Gain percentage = {(30a – 27a)/27a} × 100 = 100/9 = 11.11%


text:
function pointer container using Boost Bind

This topic is 3326 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I am trying to call the function(consoleSetRenderMode()) once i get a string called "setRenderMode" but i get compilation errors :( #include <boost/any.hpp> #include <boost/function.hpp> #include <boost/bind.hpp> #include <map> #include <string> #include <vector> #include <iostream> using namespace std; typedef std::vector<boost::any> parameters; typedef boost::function<void(const parameters&)> consoleFunc; typedef std::map<std::string, consoleFunc> consoleFuncMap; consoleFuncMap consoleFuncs; void consoleSetRenderMode(const boost::any ); void consoleSetRenderMode(const parameters ¶ms) { assert(params.size() == 1); // should have 1 parameter int renderMode = boost::any_cast<int>(params[0]); cout<<"Val"<<renderMode<<endl; //renderer->setRenderMode(renderMode); } consoleFuncs["setRenderMode"] = boost::bind(&consoleSetRenderMode, _1);

Share on other sites
You don't need to use boost::bind if your function signature already matches the function type. However, since your function is overloaded, you do need to disambiguate the function overload. Ex:
consoleFuncs["setRenderMode"] = static_cast<void (*)(const parameters &)>(consoleSetRenderMode);

Share on other sites
Quote:
 void consoleSetRenderMode(const boost::any );void consoleSetRenderMode(const parameters ¶ms)

Two functions with the same name and different parameters are overloaded functions. Also, you can't assign elements in a map outside of a function like that. One way to deal with that is to move the assignments to inside main.

Share on other sites
No, your typedef for parameters is std::vector<boost::any>, not boost::any. And even if it was the same, the first one is by value and the second by reference.

Share on other sites
What exactly is the logic behind deleting all your replies here?

Share on other sites
to make the post look clear and short

Share on other sites
Quote:
 Original post by himanojhereto make the post look clear and short

Your definition of "clear" is defective.

Share on other sites
can we get back to the problem

Share on other sites
How? You deleted your responses. Kind of hard to comment on something that's not there.

Share on other sites
What was wrong with SiCrane's original response? That seems like the correct answer to me.
Quote:
Original post by SiCrane
Quote:
 void consoleSetRenderMode(const boost::any );void consoleSetRenderMode(const parameters ¶ms)

Two functions with the same name and different parameters are overloaded functions. Also, you can't assign elements in a map outside of a function like that. One way to deal with that is to move the assignments to inside main.

• 16
• 9
• 13
• 41
• 15


text:
+0

0
511
1

What is the smallest integer $n$, greater than $1$, such that $n^{-1}\pmod{1320}$ is defined?

May 21, 2019

#1
+25228
+3

What is the smallest integer n, greater than 1, such that $$n^{-1}\pmod{1320}$$is defined?

According to Euler's theorem, if a is coprime to m, that is, gcd(a, m) = 1, then
$${\displaystyle a^{\phi (m)}\equiv 1{\pmod {m}},}$$
where  $${\displaystyle \phi }$$   is Euler's totient function.
A modular multiplicative inverse can be found directly:
$${\displaystyle a^{\phi (m)-1}\equiv a^{-1}{\pmod {m}}.}$$
n must be coprime to 1320 or gcd(n,1320) = 1,

Factorization of 1320:

$$1320 = 2^3×3×5×11$$ (6 prime factors, 4 distinct)

The smallest integer n > 1 coprime to 1320 is 7.

$$\begin{array}{|rcll|} \hline && 7^{-1}{\pmod {1320}} \\ &\equiv& 7^{\phi (1320)-1}{\pmod {1320}} \quad | \quad \phi (1320) = 320 \\ &\equiv& 7^{320-1}{\pmod {1320}} \\ &\equiv& 7^{319}{\pmod {1320}} \\ &\equiv& \mathbf{943} {\pmod {1320}} \\ \hline \end{array}$$

May 21, 2019
edited by heureka  May 22, 2019


text:
# On the displacement of a permutation

Could you help me to prove this: $\pi\in S_n$, we define the displacement of $\pi$ as $\mathrm{disp}(\pi)=\sum_{i=1}^n|\pi(i)-i|$. I have to prove the following:

$\mathrm{disp}(\pi)$ is always even.

-
I must be misunderstanding (2). I tried to do an example for $n=3$. There are 6 permutations in $S_3$. Written as products of transpositions they are: (1) (disp=0), (12) (disp=2), (13) (disp=4), (23) (disp=2), (12)(23) (disp=4), and (13)(23) (disp=6). So for $k=2$, I compute $e_{n,k}-o_{n,k}=1-1=0 \neq 1 = (-1)^k \binom{n-1}{k}$. Is the problem correct as stated, or am I just confused? –  Dimitrije Kostic Nov 16 '11 at 4:48
@DimitrijeKostic: The last two perms should be (123) and (132), both with disp=4. The first perm and the last 2 perms are even; the others are odd. So we have $e_{3,k}=(1,0,2)$ and $o_{3,k}=(0,2,1)$ for $k=0,1,2$. This matches the identity. –  David Bevan Nov 16 '11 at 12:11
@DavidBevan Thanks, I see my error now. –  Dimitrije Kostic Nov 16 '11 at 15:43

For the first part, note that the parity of $|x-y|$ equals the parity of $x-y$, so the parity of disp$(\pi)$ equals the parity of $\sum(\pi(i)-i)=\sum\pi(i)-\sum i=0$, and $0$ is even.


text:
# unmtr#

Multiplies a complex matrix by the complex unitary matrix Q determined by hetrd.

Description

unmtr supports the following precisions.

T

std::complex<float>

std::complex<double>

The routine multiplies a complex matrix $$C$$ by $$Q$$ or $$Q^{H}$$, where $$Q$$ is the unitary matrix $$Q$$ formed by hetrd when reducing a complex Hermitian matrix $$A$$ to tridiagonal form: $$A = QTQ^H$$. Use this routine after a call to hetrd.

Depending on the parameters side and trans, the routine can form one of the matrix products $$QC$$, $$Q^{H}C$$, $$CQ$$, or $$CQ^{H}$$ (overwriting the result on $$C$$).

## unmtr (Buffer Version)#

Syntax

namespace oneapi::mkl::lapack {
void unmtr(cl::sycl::queue &queue, oneapi::mkl::side side, oneapi::mkl::uplo upper_lower, oneapi::mkl::transpose trans, std::int64_t m, std::int64_t n, cl::sycl::buffer<T,1> &a, std::int64_t lda, cl::sycl::buffer<T,1> &tau, cl::sycl::buffer<T,1> &c, std::int64_t ldc, cl::sycl::buffer<T,1> &scratchpad, std::int64_t scratchpad_size)
}

Input Parameters

In the descriptions below, r denotes the order of $$Q$$:

$$r$$=$$m$$

if side = side::left

$$r$$=$$n$$

if side = side::right

queue

The queue where the routine should be executed.

side

Must be either side::left or side::right.

If side=side::left, $$Q$$ or $$Q^{H}$$ is applied to $$C$$ from the left.

If side=side::right, $$Q$$ or $$Q^{H}$$ is applied to $$C$$ from the right.

upper_lower

Must be either uplo::upper or uplo::lower. Uses the same upper_lower as supplied to hetrd.

trans

Must be either transpose::nontrans or transpose::conjtrans.

If trans=transpose::nontrans, the routine multiplies $$C$$ by $$Q$$.

If trans=transpose::conjtrans, the routine multiplies $$C$$ by $$Q^{H}$$.

m

The number of rows in the matrix $$C$$ ($$m \ge 0$$).

n

The number of columns the matrix $$C$$ ($$n \ge 0$$).

k

The number of elementary reflectors whose product defines the matrix $$Q$$ ($$0 \le k \le n$$).

a

The buffer a as returned by hetrd.

lda

The leading dimension of a $$(\max(1,r) \le \text{lda})$$.

tau

The buffer tau as returned by hetrd. The dimension of tau must be at least $$\max(1,r-1)$$.

c

The buffer c contains the matrix $$C$$. The second dimension of c must be at least $$\max(1,n)$$.

ldc

The leading dimension of c $$(\max(1,n) \le \text{ldc})$$.

Size of scratchpad memory as a number of floating point elements of type T. Size should not be less than the value returned by unmtr_scratchpad_size function.

Output Parameters

c

Overwritten by the product $$QC$$, $$Q^{H}C$$, $$CQ$$, or $$CQ^{H}$$ (as specified by side and trans).

Buffer holding scratchpad memory to be used by routine for storing intermediate results.

Throws

This routine shall throw the following exceptions if the associated condition is detected. An implementation may throw additional implementation-specific exception(s) in case of error conditions not covered here.

oneapi::mkl::unimplemented

oneapi::mkl::unsupported_device

oneapi::mkl::lapack::invalid_argument

oneapi::mkl::lapack::computation_error

Exception is thrown in case of problems during calculations. The info code of the problem can be obtained by info() method of exception object:

If $$info=-i$$, the $$i$$-th parameter had an illegal value.

If info equals to value passed as scratchpad size, and detail() returns non zero, then passed scratchpad is of insufficient size, and required size should not be less than value return by detail() method of exception object.

## unmtr (USM Version)#

Syntax

namespace oneapi::mkl::lapack {
cl::sycl::event unmtr(cl::sycl::queue &queue, oneapi::mkl::side side, oneapi::mkl::uplo upper_lower, oneapi::mkl::transpose trans, std::int64_t m, std::int64_t n, T *a, std::int64_t lda, T *tau, T *c, std::int64_t ldc, T *scratchpad, std::int64_t scratchpad_size, const std::vector<cl::sycl::event> &events = {})
}

Input Parameters

In the descriptions below, r denotes the order of $$Q$$:

$$r$$=$$m$$

if side = side::left

$$r$$=$$n$$

if side = side::right

queue

The queue where the routine should be executed.

side

Must be either side::left or side::right.

If side=side::left, $$Q$$ or $$Q^{H}$$ is applied to $$C$$ from the left.

If side=side::right, $$Q$$ or $$Q^{H}$$ is applied to $$C$$ from the right.

upper_lower

Must be either uplo::upper or uplo::lower. Uses the same upper_lower as supplied to hetrd.

trans

Must be either transpose::nontrans or transpose::conjtrans.

If trans=transpose::nontrans, the routine multiplies $$C$$ by $$Q$$.

If trans=transpose::conjtrans, the routine multiplies $$C$$ by $$Q^{H}$$.

m

The number of rows in the matrix $$C$$ ($$m \ge 0$$).

n

The number of columns the matrix $$C$$ ($$n \ge 0$$).

k

The number of elementary reflectors whose product defines the matrix $$Q$$ ($$0 \le k \le n$$).

a

The pointer to a as returned by hetrd.

lda

The leading dimension of a $$(\max(1,r) \le \text{lda})$$.

tau

The pointer to tau as returned by hetrd. The dimension of tau must be at least $$\max(1,r-1)$$.

c

The array c contains the matrix $$C$$. The second dimension of c must be at least $$\max(1,n)$$.

ldc

The leading dimension of c $$(\max(1,n) \le \text{ldc})$$.

Size of scratchpad memory as a number of floating point elements of type T. Size should not be less than the value returned by unmtr_scratchpad_size function.

events

List of events to wait for before starting computation. Defaults to empty list.

Output Parameters

c

Overwritten by the product $$QC$$, $$Q^{H}C$$, $$CQ$$, or $$CQ^{H}$$ (as specified by side and trans).

Pointer to scratchpad memory to be used by routine for storing intermediate results.

Throws

This routine shall throw the following exceptions if the associated condition is detected. An implementation may throw additional implementation-specific exception(s) in case of error conditions not covered here.

oneapi::mkl::unimplemented

oneapi::mkl::unsupported_device

oneapi::mkl::lapack::invalid_argument

oneapi::mkl::lapack::computation_error

Exception is thrown in case of problems during calculations. The info code of the problem can be obtained by info() method of exception object:

If $$info=-i$$, the $$i$$-th parameter had an illegal value.

If info equals to value passed as scratchpad size, and detail() returns non zero, then passed scratchpad is of insufficient size, and required size should not be less than value return by detail() method of exception object.

Return Values

Output event to wait on to ensure computation is complete.


text:
Question

# A bag contains $8$red and $7$black balls. Two balls are drawn at random. Find the probability that the both balls are of the same color.

Verified
130.2k+ views
Hint: Probability is simply how likely something is to happen. Whenever we are unsure about the outcome of an event, we can talk about the probabilities of certain outcomes and how likely they are.
Probability of an event is a number between $0$& $1$.
Probability of an event is given below by :
$Probability\, = \,\dfrac{{Possible\,outcomes}}{{Total\,outcomes}}$.
In such questions for a solution we will use combinations.

Complete step by step solution:
Given,
A bag containing $8$red $7$black balls.
No. of balls drawn from the bag $= \,2$.
Total number of balls $=$Red balls $+$Black balls.
$= \,\,8\, + \,7$
$= \,15$balls.
Two balls are drawn randomly. We need to find the probability that both balls are of the same color i.e. either both are red or both are black.
We have,
Number of ways of drawing $2$balls from $15$balls.
$= \,{}^{15}{C_2}$
$\left[ {{}^n{C_r} = \dfrac{{n\,!}}{{r\,!\left( {n - r} \right)\,!}}} \right]$
$= {}^{15}{C_2} = \dfrac{{15\,!}}{{2\,!\left( {15 - 2} \right)\,!}} = \dfrac{{15\,!}}{{2\,!\,\, \times 13\,!}}$
$= \,\dfrac{{15 \times 14 \times 13!}}{{2 \times 1 \times 13\,!}}$ $\left[ {\because n\,!\, = \,n\, \times \,\left( {n - 1} \right) \times x\left( {n - 2} \right)......} \right]$
$= \,\dfrac{{15 \times 14}}{2} = 15 \times 7 = 105$ways. _____(1).
First case:
NO. of ways of drawing $2$red balls $= {}^8{C_2}$
$= \dfrac{{8!}}{{2!\left( {8 - 2} \right)!}}$
$\left[ {{}^n{C_r} = \dfrac{{n\,!}}{{r\,!\left( {n - r} \right)\,!}}} \right]$
$= \dfrac{{8!}}{{2! \times 6!}} = \dfrac{{8 \times 7 \times 6!}}{{2 \times 1 \times 6!}}$
$= \dfrac{{8 \times 7}}{2} = 4 \times 7 = 28$ways. _________ (2).
Second case:
No. of ways of drawing $2$black balls $= {}^7{C_2}$
$= \dfrac{{7!}}{{2!\left( {7 - 2!} \right)}}$
$\left[ {{}^n{C_r} = \dfrac{{n\,!}}{{r\,!\left( {n - r} \right)\,!}}} \right]$
$= \dfrac{{7!}}{{2! \times 5!}} = \dfrac{{7 \times 6 \times 5!}}{{2 \times 1 \times 5!}}$
$= \dfrac{{7 \times 6}}{2} = 7 \times 3 = 21$ways. _________ (3).
Hence, Probability of drawing balls of same color
$= \dfrac{{Probability\,that\,both\,are\,red + Probability\,that\,both\,are\,black}} {{Probability\,of\,drawing\,2\,balls\,at\,all\,from\,total}}$
$= \dfrac{{28 + 21}}{{105}}$ [from equations 1, 2, & 3]
$= \dfrac{{49}}{{105}}$$= \dfrac{7}{{15}}$.

Note: We see combinations when we need to select things.
When selecting/choosing something never confuse it with permutation
Solution of r things from n things is ${}^n{C_r} = \dfrac{{n!}}{{r!\left( {n - r} \right)!}}$.


text:
# How to get high current from 9 volt batteries

I am planning to make a solenoid.. Which should be so powerful as to lift up about 600N force. I have thought about it, and I have a doubt. How can I get DC currents up to 20-30 A using a 9 V battery? Please suggest a way I can set them up in a way that would give enough current.

Another question, I thought about stepping up the voltage for a larger current. Would that work?

• Increasing the voltage decreases the current available. Jun 18 '13 at 5:35
• google.com/search?q=flash+circuit Jun 18 '13 at 5:36
• Only way to get high current from 9 V batteries is to connect large number of them in parallel, but that would have it's own down-sides. Really, 9 V batteries are extremely poor source of power. If you need current, get rechargeable 12 V battery or some lithium-polymer batteries. They'll be much cheapr in the long run. Jun 18 '13 at 6:01
• What is the dc resistance of your solenoid and what is the capacity of your 9V battery and type. Jun 18 '13 at 7:15
• You would need a really big 9V battery. Stepping up the voltage makes the problem worse, not better, if it's the current you are about. Aug 21 '19 at 14:58

A 9V battery has approximately a stored energy of:

$$\require{cancel} \frac{560\cancel{m}A\cancel{h} \cdot 9V}{1} \frac{3600s}{\cancel{h}} \frac{1}{1000\cancel{m}} \approx 18144VAs \approx 18 kJ$$

A joule is a watt-second, or a newton-meter. Under the most ideal conditions, with perfectly efficient machines everywhere, there is enough stored energy in a 9V battery to apply your specified 600N force over a distance of:

$$\frac{18\cancel{k}\cancel{J}}{1} \frac{\cancel{N}m}{\cancel{J}} \frac{1}{600\cancel{N}} \frac{1000}{\cancel{k}} = 30m$$

Your proposed solenoid, requiring maybe $25A$ at $9V$, consumes electrical power at the rate of:

$$25A \cdot 9V = 225W$$

Applying your specified $600N$ force, and given that power, we can solve for the velocity your solenoid, were it 100% efficient, could provide:

$$\frac{225\cancel{W}}{1} \frac{\cancel{J}}{\cancel{W}s} \frac{\cancel{N}m}{\cancel{J}} \frac{1}{600\cancel{N}} = 0.375m/s$$

So you see, even if we can extract all the stored energy of the 9V battery with 100% efficiency, there isn't a whole ton of it. Knowing that your ideal solenoid is moving at $0.375m/s$, and that the battery has enough energy for it to move $30m$, the runtime is:

$$\frac{30\cancel{m}}{1} \frac{s}{0.375\cancel{m}} = 80s$$

Or we could calculate it from the battery energy and solenoid power:

$$\frac{18000\cancel{W}s}{1} \frac{1}{225\cancel{W}} = 80s$$

But maybe it's enough. The question is how to do it efficiently. Electrical power in a resistance is given by:

$$P = I^2 R$$

The internal resistance of a 9V battery is maybe $1.5\Omega$, when fresh. It goes up as the battery drains. Your solenoid is probably at least another $1\Omega$. So at $25A$, your resistive losses alone would be:

$$(25A)^2 (1.5\Omega + 1\Omega) = 1562.5W$$

Compare this to the power used by the ideal solenoid considered above ($225W$) and you can see this is an absurdly inefficient system. Just dealing with the heat from these losses will be a challenge. Of course, you can't actually get this out of a 9V battery, because the voltage lost over its internal resistance at $25A$ is:

$$25A \cdot 1.5\Omega = 37.5V$$

...which is more than the 9V supplied by the battery.

Besides the battery, or the solenoid, transferring $225W$ of electrical power is a problem itself. Because power is the product of voltage and current ($P=IE$), to move a lot of power you can have high current, or high voltage. But, even wires have resistance, and since power lost to this resistance is proportional to the square of current, it's more practical to move high amounts of electrical power at high voltage than it is at high current. This is why the electric utility transmits power over long distances at very high voltage.

So, if you want to move $225W$ at $9V$, you must keep the resistance very low, to avoid resistive losses from being very high. That means fat wire (including the wire in your solenoid, which accounts for most of the wire in the circuit) and batteries with low internal resistance. You can also trade current for voltage, or voltage for current, in the design of your solenoid, as supercat's answer describes.

• Thank you for answering this from an ESR standpoint. Too many people look at batteries as ideal voltage sources, and miss important effects of actual batteries, particularly highly compromised types like the common 9V and coin cells. Jun 18 '13 at 16:39

Since you haven't specified, I'd assume that you mean a household, commercially available 9V battery. A standard 9V battery has about 400-600 mAh capacity. In the most basic terms, these batteries can supply about 500 milliamps for one hour before being "dead". You could, in theory, draw the current you are looking for, but even for several 9V batteries in parallel (sums the capacity), you'd get around 1-2 minutes from each set of batteries. With standard consumer batteries, that's pretty unrealistic, and pretty inefficient. I can imagine that you probably don't want to be changing batteries every minute.

If size and weight aren't huge factors, I'd look into large, high capacity, fast-discharge lead acid batteries. They come in 12V, which is close to what you're looking for, and can supply hundreds of amps of current for varying amounts of time (depending on how much you spend/which battery you get).

• The OP hasn't said (yet) what the battery is and therefore your answer presupposes that it is a "standard" type. You may be correct in your assumption but you may not be. Jun 18 '13 at 7:17
• Excellent point. Edited my answer a bit. Jun 18 '13 at 14:39

The design of a solenoid is a trade-off between using more turns versus using more current. I really doubt that any solenoid small which is small enough that one could realistically operate it off a 9-volt battery would achieve optimal behavior with a current as high as you suggest. Efficiency would most likely be better using more turns.

That having been said, the maximum solenoid current that can be gotten from a 9-volt battery would be obtained by connecting a capacitor in parallel with the battery, and then using a couple of efficient switches to alternately connect the solenoid to the battery and short it out (one must avoid ever having both switches closed, and should minimize the amount of time both are open; use a flyback diode to safely dissipate energy during the "both open" time). To absolutely maximize solenoid current without regard for battery life, set ratio of battery time to "shorting time" so that the battery is drawn down to about 4.5 volts. That will draw maximum power out of the battery, even though it will cause the battery to waste about half of its energy heating itself. Setting the ratio a bit lower, so it only draws the battery down to 6 volts, will reduce the coil current slightly (by about 12%) but improve battery life by 50%, since only a third of the battery's energy will be wasted in self-heating.

Using a 9V battery imples using one, single, 9V battery.

If that is not a real constraint you are working under, I recommend serially connecting several to achieve a higher voltage. If you can only use one single 9V battery, I recommend acquiring a high-capacitance capacitor and charging it through a current-limiting circuit, then switching it to power your solenoid. This will not give a sustained output, but depending on circuit and solenoid, it should give you 600 N

Use two IMR high drain lithium batteries in series. Sizes 18650 to 26650 or more can deliver currents as high as 60 amps. If voltage is too low (8.4) you can use LiFePo batteries for 9.6 volts, (3 times 3.2 volts).


text:
Only harmonics of the same frequency interact to produce:

Free Practice With Testbook Mock Tests

Options:

1. Average power

2. Total power

3. dc power

4. ac power

Correct Answer: Option 1 (Solution Below)

This question was previously asked in

LMRC Assistant Manager (S&T) Official Paper: (Held on 20 Jan 2020)

Solution:

To determine the instantaneous power p(t) absorbed by an element, the Fourier series for the current and the Fourier series voltage for the element are multiplied.

To determine the average power of a resistor, we simply integrate and divide by the period as shown:

$${p_{avg}} = \frac{1}{T}\;\mathop \smallint \limits_{{t_0}}^{{t_0} + T} {x^2}\left( t \right).dt$$

$$= \frac{1}{T}\mathop \smallint \limits_{{t_0}}^{{t_0} + T} \frac{{v_0^2\left( t \right)}}{R} \cdot dt$$

$${p_{avg}} = \frac{{{i_0}{v_0}}}{4} + \frac{1}{2}\;\mathop \sum \limits_{n = 1}^\infty {i_n}{v_n}\cos \left( {{\theta _n} - {\theta _n}} \right)$$

In the above equation only identical frequencies or Harmonics with the same frequencies interact to produce average power.


text:
# On Giving Too Much Legitimacy to the Inferior Position

You find an ant mound in your house. Would you call an exterminator to remove it? Or would you treat it with “dignity” and offer to fight it in a “fair” duel?

There is something fundamentally wrong with the way arguments and debate work in modern society. Whereas the common sense choice is simply to remove the ant mound as fast as possible, the politically correct choice is to hear “both sides” of the story, run smear campaigns against the ant mound while defending against verbal insults made on yourself, and then put the ultimate decision to a referendum of not-the-most-intelligent voters, hoping they side with you and not the swarm of ants.

Debates and arguments are more focused today on winning vs. losing, not on right vs wrong, or truth vs fiction, or reason vs insanity.

The Appeal to Image

An enormous problem with this style of debate is that it gives too much legitimacy to the inferior position. A debate should focus on drawing logical conclusions from facts, not on maintaining personal reputations. For nearly all publicized debates, winning is glorified and losing is stigmatized.

Yet in the scientific disciplines, losing happens all the time, and if the loser is able to admit it, he is the one who actually learns more from the debate by discarding his outdated or incorrect theory, and progressing forward with a better one.

To quote Carl Sagan:

In science it often happens that scientists say, ‘You know that’s a really good argument; my position is mistaken,’ and then they would actually change their minds and you never hear that old view from them again. They really do it. It doesn’t happen as often as it should, because scientists are human and change is sometimes painful. But it happens every day. I cannot recall the last time something like that happened in politics or religion.

In math, it is even better. You only need to come up with a correct proof or disproof, and every reasonable mathematician will agree with the correct side. There is literally no legitimate argument for the other side, because logically, it cannot exist.

Consider the equation 0.999… = 1. There is no ambiguity of truth to this statement. It can be proved many, many ways, though even one way is enough. We cannot pass such a statement to a referendum for a popular vote, as it is conceivable that the majority of the population will vote that the statement is false, yet among mathematicians, the vote will be unanimous for truth.

The act of even putting “False” on the ballot in the first place would be misleading to a non-mathematical voter. If I didn’t know enough math to deduce the truth of the statement, and all I saw on the ballot were “True” and “False,” I would probably think: “Well, since these positions are even on the ballot in the first place, it probably means there are some mathematicians arguing for ‘True’ and some arguing for ‘False.’ That means I need to use my own math skill. Hmm, obviously 0.9 is less than 1, 0.99 is less than 1, 0.999 is less than 1, so 0.999… is less than 1. I vote ‘False.’ ”

Yet, no one goes around protesting that the “other side” of this argument should be taught in schools, as whether 0.999… = 1 is irrelevant to their beliefs. When it comes to biology though, it becomes different.

Probably the most ridiculous instance of giving too much legitimacy to the inferior position is the evolution vs creationism “debate.” Just as among mathematicians there is no debate as whether 0.999… = 1, there is no debate among biologists as to whether evolution or creation led to where we are. By no debate, we mean that at least 99.85% of scientists in the earth and life sciences agree with evolution. Although, from just looking at the media, one might not expect this to be the case. Same with huge wastes of time and money that shouldn’t have even existed. There’s a difference between teaching true controversy and the disgrace of “Teach the Controversy,” which is just “Teach the Idiocy.”

It is much worse in religious debates, as religion somehow has a magical spell protecting it from all criticism. You’re encouraged to disagree all you want about musical taste, food, fashion, and even politics, but the moment anything remotely close to religion is debated, it is “offensive” and “disrespectful.” Other than due to an unfortunate social norm, Why? Why is it acceptable for an uneducated person to vocally disagree with scientists about matters of science and have their own article about it in the news, yet it is unacceptable for even an intellectual to disagree regarding religion?

It’s almost like a self-fulfilling prophecy. Anything they say must be respected, so they can make intolerant statements such as saying all people who disagree with them are fools, and as an audience we’re supposed to respect that. Just why? If an ignorant person calls you a fool, you have no responsibility to respect that opinion.

The Freedom of Speech

But we have the freedom of speech, you might say. We can say whatever we want.

Indeed, I think free speech is one of the most important features of an advanced, civilized society. (The lack of free speech is one of the reasons I despise modern China.) But there’s a difference between having the right to say whatever you want and the right to force an ignorant belief onto other people. Free speech lets you say the Earth is flat without being arrested by the government. But it sure doesn’t let you force the Flat-Earth theory into textbooks in public education. Or astrology. Or slavery. Or the 2012 doomsday.

Dissent from oppression is imperative. Dissent from authority is necessary. But dissent from truth is blindness. No matter how much one might protest the truth, the truth stays put. It is we who must adapt to the truth, not adapt the truth for us. The Freedom of Speech is not the Freedom to Brainwash.

Even the act of having to write this post deeply upsets me. Ideally this should all be Common Sense, yet Thomas Paine seems to have been all but forgotten by the inhabitants of America.

Seems like it’s about time for another Enlightenment, another Age of Reason.

# Quote Mismatched

Can you correctly match the following quotes with their authors?

1. Those people who think they know everything are a great annoyance to those of us who do.
2. The empires of the future are the empires of the mind.
3. Those who can make you believe absurdities can make you commit atrocities.
4. All art is quite useless.
5. Faith, as such, is extremely detrimental to human life: it is the negation of reason.
6. If the people cannot trust their government to do the job for which it exists – to protect them and to promote their common welfare – all else is lost.
7. Capitalism has worked very well. Anyone who wants to move to North Korea is welcome.
8. You can tell more about a person by what he says about others than you can by what others say about him.
9. The word god is for me nothing more than the expression and product of human weaknesses, the Bible a collection of honourable, but still primitive legends which are nevertheless pretty childish.
10. Men are moved by two levers only: fear and self interest.

The choices, each used exactly once, are:

• Albert Einstein
• Napoleon Bonaparte
• Isaac Asimov
• Bill Gates
• Barack Obama
• Oscar Wilde
• Ayn Rand
• Voltaire
• Audrey Hepburn
• Winston Churchill

The answer key is found here, but try it yourself first! If you really are bold, I dare you to write down your guesses in the comments and then check the solution.

# How to (Theoretically) Win a 2-Party Presidential Election with Just 21.8% of the Popular Vote

In an extreme case, consider the following electoral map:

Of course, this is nonsensical as DC is red and Texas is blue, but let’s assume this happened for the sake of argument. Despite the map being overwhelmingly red, the red states win the electoral vote by only the slightest margin of 270 to 268.

Let us assume that every single state was nearly evenly split, something like 50.01% to 49.99%. Then even though the red states won the electoral vote, the blue states contain 56.4% of the population, thus the blue candidate actually wins the popular vote 56.4% to 43.6%, a huge lead.

Now, suppose the vote was nearly even in the red states, but let the blue candidate win 100% of the vote in all the blue states. Then the red candidate wins only 21.8% of the popular vote, yet still wins the election, despite 78.2% of the electorate voting against him.

List of states in our hypothetical model: Red – Wyoming, District of Columbia, Vermont, North Dakota, Alaska, Rhode Island, South Dakota, Delaware, New Hampshire, Montana, Maine, Hawaii, Nebraska, West Virginia, Idaho, New Mexico, Nevada, Utah, Kansas, Arkansas, Mississippi, Iowa, Connecticut, South Carolina, Minnesota, Alabama, Oklahoma, Kentucky, Oregon, Colorado, Washington, Louisiana, Wisconsin  Maryland, Tennessee, Arizona, Indiana, Massachusetts, Missouri, and North CarolinaBlue – Virginia, Michigan, New Jersey, Pennsylvania, Georgia, Ohio, Illinois, Florida, Texas, New York, and California.

Note: After I wrote this post, I googled the 21.8% and found a few cases where people used intense computer computation with exponential-time algorithms to figure this out.

I was shocked when I discovered these methods, as my own method was extraordinarily simple, taking all of two minutes in Excel, with otherwise no number-crunching: just list out the states in ascending order of population per electoral vote, and then go down the list until you get to 270 or more. The list I got started with Wyoming, and went all the way down to Georgia. However, this added up to 271, so I searched for any way to shave off 1 electoral vote. As it turns out, there was a way: I replaced Georgia (16 electoral votes) by North Carolina (15 electoral votes), which has a smaller population.

Bonus Round #1:

Now pretend there are more than 2 parties. Then it is possible to win 270 with an even smaller percentage of the popular vote. Let n be the number of parties. Then you can win with 43.6/n % of the popular vote. The 2-party example of 21.8% is just a special case of this. For example, with 3 parties the red candidate just needs to win a 33.34% vs 33.33% vs 33.33% plurality in each of the required states, so to win the presidency, he only needs to win 43.6/3 %, or 14.5%, of the popular vote.

Bonus Round #2:

What if the electoral college reps were voted in based on district? The representatives are based on members of congress, right? So what if every state did what Maine and Nebraska does and allow their representatives to split? Two elected based on statewide votes, the rest by congressional district. Keeps the small states relevant to the campaign while making the electoral process more representative.

As it turns out, the answer doesn’t change if we let electors vote by district. Just let the red candidate win every single district in every single red state listed above by one vote. Then it’s still an electoral win with 21.8% of the popular vote.

The number does change, however, if we remove the two state votes from each state and have the vote counted purely by district. Then a candidate must win 23.2% of the popular vote (win the 219 smallest districts by a marginal amount, outright lose the other 217 districts).

Sources:

# The Perfect Prediction

Many have heard of Nate Silver’s prediction of the 2012 presidential election. For those of you who haven’t seen it yet, here was his prediction for last Tuesday, which may seem uncannily familiar:

It seems familiar because it bears a striking resemblance the actual results:

In fact, that’s all 50 states correctly predicted.

Given two equally likely options for each states, the chance to predict all 50 states correctly is one in $2^{50}$, or one in 1.126 quadrillion. Granted, we already knew which direction states like Texas or Vermont would vote for, so for the sake of simplicity let’s consider only the 9 “swing” states: Colorado, Florida, Iowa, Nevada, New Hampshire, North Carolina, Ohio, Virginia and Wisconsin. That’s still a one in 512 chance to guess all 9 states correctly from sheer luck.

How did he do it? The answer is high-caliber aggregate statistics. When you conduct a poll, you are going to have very high uncertainty if you poll only a few people. But if you poll a lot of people, your prediction gets more accurate. And one way to poll many people at once is to aggregate the data from many, many polls.

In 2008, Silver’s prediction was accurate in 49 of the 50 states, missing only Indiana.

# Does Your Individual Vote Really Matter?

Everyone on Facebook seems to be talking about how they voted today, and why you should as well. To be a good citizen, they say, you must vote. “Go vote!” says every other status on my Facebook feed.

Yet there are plenty of reasons not to vote, and in fact, not voting has been historically a very powerful form of protest against a government. This article debunks many of the voting myths that attempt to place voting on the moral high-ground. I found the most significant part of the article to be number 5, which responds to the claim that your vote is your voice in the government:

In a democratic form of government it would be. In a democratic form of government, such as a direct or participatory democracy, people can vote on things like budgets, wars, and other important issues, and have a voice in government. In our representative government, people can only vote for representatives who may or may not listen to them or act in their interests, and who cannot be held accountable during their terms of office, which is the only time they hold power and are needed to represent the interests of their constituents. Waiting until somebody has killed a million people in a war based on lies, destroyed the economy, and taken away your civil rights, and then trying to elect somebody else, is much too late because by then much of the damage cannot be undone and your grandchildren will still be paying for it.

Indeed, the United States is not a true democracy (though the term “democracy” gets thrown around enough that it seems to be synonymous with anything moral).

There are two more main reasons why, for the majority of voters, your vote will be futile. Firstly, the electoral college system places all importance on the swing states such as Ohio. Unless you live in one of these states, your individual vote will have nearly zero chance of affecting the outcome of the election, as the vote of your state is already determined. Even if you do live in one of these states, one vote will not statistically make a difference. There has not ever been a case where a president has been decided by one vote, and basic probability tells you it will remain that way.

But what if everyone thinks like that, you might say. If everyone does this, then no one will vote, and the election will fail. The bad guy will be elected with just a handful of votes.

This is hardly a valid concern. We all agree that being a medical doctor is a good and respectable profession. However, if everyone thinks like that, then everyone will be doctors, and nobody will be there to grow crops, educate children, provide entertainment, forecast weather, write books, or produce art. This argument fails because even though one might respect doctors, one must not necessarily become one.

Secondly, if you really want to change the world, you’re not going to do it by casting a single ballot once and then posting once on Facebook that you voted and then never mention politics again. Suppose I had a button in front of me such that every time I pressed the button, it would add one vote randomly for Barack Obama or Mitt Romney in a random polling booth in the United States. Even if I pressed the button a thousand times it would have no statistical effect on the outcome.

If you want to change something, start a movement. Your government won’t listen to an insignificant statistic in a polling booth, but it sure as hell will listen to a provocative demonstration. The beauty of the United States is that you have the right to challenge the government, a right that is too often taken for granted, for in many countries, speaking out against the slightest flaw in your country could be a death sentence. So exercise this right! We the people control the government, yet we have allowed the government to control us.

So if you think that by voting, you have fulfilled your civic duty for the next four years, think again. If you really care about your country that much, you would do a lot more than broadcasting your vote on Facebook to a bunch of people you already know anyways.

All that said, in an age of technology and reason, I would be very unhappy if Romney were elected. It is important that the United States lead the world in advancing forward, not regressing back into an anti-intellectual dark age. If I were to choose between Romney and Obama, I would without the slightest hesitation pick President Obama. However, given that Ithaca, NY is guaranteed to vote Democrat (and the state of New York as a whole), and given that both major party candidates have been quiet about the environment in the weeks leading up to the election, my vote today went to Green Party candidate Jill Stein.

# Blogging Year 3

Today is the 3rd birthday of my blog! It was a fairly light year, with only 42 posts published, but it received 52k views, thereby averaging 1238 views per new post (many of these views were on older posts, so it is not an accurate representation of views for a given post). In comparison, Year 1 averaged 1042 views per post and Year 2 averaged 1053 [data].

The most visited posts in the third year were:

1. The Persistence of Memory – 18,465 views
3. 10 Mind Blowing Mathematical Equations – 2,506 views
4. Tumblr vs WordPress: Simplicity vs Power – 2,360 views
5. The End of an Experiment – 2,206 views
6. US Census 2010 Win – 1,699 views

The vast majority of the hits for #1 and #5 resulted from Google image searches, whereas the majority for #3 and #4 came from normal Google searches. Interesting.

Haven’t tracked followers in previous years, but as it stands, 62 of you are following this blog. Nice!

One final note: unlike in the past two years, I am not participating in Nanowrimo this year due to some very busy math classes, though I would gladly cheer on anyone who is. Good luck getting to 50,000. May the Force be with you.


text:
×

# Find the parametric equation

Hi guys i'm stuck on this problem, Find the parametric equation of the curve generated by the intersection of: $$x^{2} + y^{2} + z^{2} = a^{2}$$

and

$$x + y + z = 1$$

$$a$$ is constant

I know that is a circunference on the plane $$x+y+z=1$$ but i can't find the equation, since i don't know how to make a 3D rotation. I'm thinking on how to use the simmetry of the problem.

https://en.wikipedia.org/wiki/Differentialgeometryof_curves

http://en.wikipedia.org/wiki/Parametric_equation

Note by Felipe Sousa
3 years, 9 months ago

Sort by:

First, what is a parametrization of the intersection of the sphere $$x^2 + y^2 + z^2 = a^2$$ and the plane $$z = 1/\sqrt{3}$$? This is easy: $(x(\theta), y(\theta), z(\theta)) = \left( \sqrt{a^2 - 1/3} \cos \theta, \sqrt{a^2 - 1/3} \sin \theta, 1/\sqrt{3} \right),$ which, as we expect, is defined if and only if $$a \ge 1/\sqrt{3}$$. Now all we need to do is rotate this parametrization in the plane $$x = y$$ by a suitable angle $$\alpha = \tan^{-1} \sqrt{2}$$. But it's not quite that simple; we multiply by an initial rotation matrix $R_{xz}(\alpha) = \begin{bmatrix} \cos\alpha & 0 & \sin\alpha \\ 0 & 1 & 0 \\ -\sin\alpha & 0 & \cos \alpha \end{bmatrix},$ followed by a (counterclockwise) rotation of $$\beta = \pi/4$$ in the $$xy$$-plane: $R_{xy}(\beta) = \begin{bmatrix} \cos \beta & -\sin\beta & 0 \\ \sin\beta & \cos\beta & 0 \\ 0 & 0 & 1 \end{bmatrix}.$ Therefore the transformed parametrization is $(x'(\theta), y'(\theta), z'(\theta)) = R_{xy}(\pi/4) R_{xy}(\tan^{-1}\sqrt{2}) \cdot (x(\theta), y(\theta), z(\theta)),$ which gives \begin{align*} x'(\theta) &= \frac{1}{3}\left( 1 + \sqrt{6a^2-2} \cos(\theta+\frac{\pi}{3}) \right), \\ y'(\theta) &= \frac{1}{3} \left(1 + \sqrt{6a^2-2} \cos(\theta-\frac{\pi}{3}) \right), \\ z'(\theta) &= \frac{1}{3} \left( 1 - \sqrt{6a^2-2} \cos\theta \right), \end{align*} for $$\theta \in [0, 2\pi)$$. It is then easy to verify that $$x' + y' + z' = 1$$ and $$x'^2 + y'^2 + z'^2 = a^2$$. Note that any such parametrization is not unique: we can find any number of equivalent parametrizations for this curve. · 3 years, 9 months ago


text:
### Comparing With RSA

Julien Cathalo, David Naccache, and Jean-Jacques Quisquater

##### Abstract

A multi-set (MS) is a set where an element can occur more than once. MS hash functions (MSHFs) map MSs of arbitrary cardinality to fixed-length strings. This paper introduces a new RSA-based MSHF. The new function is efficient and produces small hashes. We prove that the proposed MSHF is collision-resistant under the assumption of unforgeability of deterministic RSA signatures. In many practical applications, programmers need to compare two (unordered) sets of integers. A trivial solution consists in sorting both sets ($\mathcal{O}(n \log n)$) and comparing them linearly. We show how MS hash functions can be turned into a linear-time, constant-space integer set equality test.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
RSASet Equality Problem
Contact author(s)
david naccache @ ens fr
History
Short URL
https://ia.cr/2009/021

CC BY

BibTeX

@misc{cryptoeprint:2009/021,
author = {Julien Cathalo and David Naccache and Jean-Jacques Quisquater},
title = {Comparing With RSA},
howpublished = {Cryptology ePrint Archive, Paper 2009/021},
year = {2009},
note = {\url{https://eprint.iacr.org/2009/021}},
url = {https://eprint.iacr.org/2009/021}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.