|
Centerpoint (geometry)
In statistics and computational geometry, the notion of centerpoint is a generalization of the median to data in higher-dimensional Euclidean space. Given a set of points in ''d''-dimensional space, a centerpoint of the set is a point such that any hyperplane that goes through that point divides the set of points in two roughly equal subsets: the smaller part should have at least a 1/(''d'' + 1) fraction of the points. Like the median, a centerpoint need not be one of the data points. Every non-empty set of points (with no duplicates) has at least one centerpoint. Related concepts Closely related concepts are the Tukey depth of a point (the minimum number of sample points on one side of a hyperplane through the point) and a Tukey median of a point set (a point maximizing the Tukey depth). A centerpoint is a point of depth at least ''n''/(''d'' + 1), and a Tukey median must be a centerpoint, but not every centerpoint is a Tukey median. Both terms are named ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Statistics
Statistics (from German language, German: ''wikt:Statistik#German, Statistik'', "description of a State (polity), state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of data. In applying statistics to a scientific, industrial, or social problem, it is conventional to begin with a statistical population or a statistical model to be studied. Populations can be diverse groups of people or objects such as "all people living in a country" or "every atom composing a crystal". Statistics deals with every aspect of data, including the planning of data collection in terms of the design of statistical survey, surveys and experimental design, experiments.Dodge, Y. (2006) ''The Oxford Dictionary of Statistical Terms'', Oxford University Press. When census data cannot be collected, statisticians collect data by developing specific experiment designs and survey sample (statistics), samples. Representative sampling as ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computational Geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity. Analysis of algorithms, Computational complexity is central to computational geometry, with great practical significance if algorithms are used on very large datasets containing tens or hundreds of millions of points. For such sets, the difference between O(''n''2) and O(''n'' log ''n'') may be the difference between days and seconds of computation. The main impetus for the development of computational geometry as a discipline was progress in computer graphics and computer-aided design and manufacturing (Computer-aided design, CAD/Compu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Median
In statistics and probability theory, the median is the value separating the higher half from the lower half of a data sample, a population, or a probability distribution. For a data set, it may be thought of as "the middle" value. The basic feature of the median in describing data compared to the mean (often simply described as the "average") is that it is not skewed by a small proportion of extremely large or small values, and therefore provides a better representation of a "typical" value. Median income, for example, may be a better way to suggest what a "typical" income is, because income distribution can be very skewed. The median is of central importance in robust statistics, as it is the most resistant statistic, having a breakdown point of 50%: so long as no more than half the data are contaminated, the median is not an arbitrarily large or small result. Finite data set of numbers The median of a finite list of numbers is the "middle" number, when those numbers are list ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Euclidean Space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean spaces of any positive integer dimension (mathematics), dimension, including the three-dimensional space and the ''Euclidean plane'' (dimension two). The qualifier "Euclidean" is used to distinguish Euclidean spaces from other spaces that were later considered in physics and modern mathematics. Ancient History of geometry#Greek geometry, Greek geometers introduced Euclidean space for modeling the physical space. Their work was collected by the Greek mathematics, ancient Greek mathematician Euclid in his ''Elements'', with the great innovation of ''mathematical proof, proving'' all properties of the space as theorems, by starting from a few fundamental properties, called ''postulates'', which either were considered as eviden ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
John Tukey
John Wilder Tukey (; June 16, 1915 – July 26, 2000) was an American mathematician and statistician, best known for the development of the fast Fourier Transform (FFT) algorithm and box plot. The Tukey range test, the Tukey lambda distribution, the Tukey test of additivity, and the Teichmüller–Tukey lemma all bear his name. He is also credited with coining the term 'bit' and the first published use of the word 'software'. Biography Tukey was born in New Bedford, Massachusetts in 1915, to a Latin teacher father and a private tutor. He was mainly taught by his mother and attended regular classes only for certain subjects like French. Tukey obtained a BA in 1936 and MSc in 1937 in chemistry, from Brown University, before moving to Princeton University, where in 1939 he received a PhD in mathematics after completing a doctoral dissertation titled "On denumerability in topology". During World War II, Tukey worked at the Fire Control Research Office and collaborated wi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Geometric Median
In geometry, the geometric median of a discrete set of sample points in a Euclidean space is the point minimizing the sum of distances to the sample points. This generalizes the median, which has the property of minimizing the sum of distances for one-dimensional data, and provides a central tendency in higher dimensions. It is also known as the 1-median, spatial median, Euclidean minisum point, or Torricelli point. The geometric median is an important estimator of location in statistics, where it is also known as the ''L''1 estimator. It is also a standard problem in facility location, where it models the problem of locating a facility to minimize the cost of transportation. The special case of the problem for three points in the plane (that is, = 3 and = 2 in the definition below) is sometimes also known as Fermat's problem; it arises in the construction of minimal Steiner trees, and was originally posed as a problem by Pierre de Fermat and solved by Evangelista Torricelli ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Helly's Theorem
Helly's theorem is a basic result in discrete geometry on the intersection of convex sets. It was discovered by Eduard Helly in 1913,. but not published by him until 1923, by which time alternative proofs by and had already appeared. Helly's theorem gave rise to the notion of a Helly family. Statement Let be a finite collection of convex subsets of , with . If the intersection of every of these sets is nonempty, then the whole collection has a nonempty intersection; that is, :\bigcap_^n X_j\ne\varnothing. For infinite collections one has to assume compactness: Let be a collection of compact convex subsets of , such that every subcollection of cardinality at most has nonempty intersection. Then the whole collection has nonempty intersection. Proof We prove the finite version, using Radon's theorem as in the proof by . The infinite version then follows by the finite intersection property characterization of compactness: a collection of closed subsets of a compact spac ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Half-space (geometry)
In geometry, a half-space is either of the two parts into which a plane divides the three-dimensional Euclidean space. If the space is two-dimensional, then a half-space is called a half-plane (open or closed). A half-space in a one-dimensional space is called a ''half-line'' or '' ray''. More generally, a half-space is either of the two parts into which a hyperplane divides an affine space. That is, the points that are not incident to the hyperplane are partitioned into two convex sets (i.e., half-spaces), such that any subspace connecting a point in one set to a point in the other must intersect the hyperplane. A half-space can be either ''open'' or ''closed''. An open half-space is either of the two open sets produced by the subtraction of a hyperplane from the affine space. A closed half-space is the union of an open half-space and the hyperplane that defines it. A half-space may be specified by a linear inequality, derived from the linear equation that specifies the defin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Euclidean Plane
In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of parallel lines, and also metrical notions of distance, circles, and angle measurement. The set \mathbb^2 of pairs of real numbers (the real coordinate plane) augmented by appropriate structure often serves as the canonical example. History Books I through IV and VI of Euclid's Elements dealt with two-dimensional geometry, developing such notions as similarity of shapes, the Pythagorean theorem (Proposition 47), equality of angles and areas, parallelism, the sum of the angles in a triangle, and the three cases in which triangles are "equal" (have the same area), among many other topics. Later, the plane was described in a so-called '' Cartesian coordinate system'', a coordinate system that specifies each point uniquely in a plane by a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor. Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is generally expresse ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Randomized Algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables. One has to distinguish between algorithms that use the random input so that they always terminate with the correct answer, but where the expected running time is finite (Las Vegas algorithms, for example Quicksort), and algorithms which have a chance of producing an incorrect result (Monte Carlo algorithms, for example the Monte Carlo algorithm for the MFAS problem) or fail to produce a result either by signaling a failure or failing to terminate. In some cases, probabilistic algorithms are the only practical means of solving a problem. In common practice, randomized algor ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Radon Point
In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that any set of ''d'' + 2 points in R''d'' can be partitioned into two sets whose convex hulls intersect. A point in the intersection of these convex hulls is called a Radon point of the set. For example, in the case ''d'' = 2, any set of four points in the Euclidean plane can be partitioned in one of two ways. It may form a triple and a singleton, where the convex hull of the triple (a triangle) contains the singleton; alternatively, it may form two pairs of points that form the endpoints of two intersecting line segments. Proof and construction Consider any set X=\\subset \mathbf^d of ''d'' + 2 points in ''d''-dimensional space. Then there exists a set of multipliers ''a''1, ..., ''a''''d'' + 2, not all of which are zero, solving the system of linear equations : \sum_^ a_i x_i=0,\quad \sum_^ a_i=0, because there are ''d'' + 2 unknow ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
