|
Geometric Discrepancy Theory
Geometric discrepancy theory is a sub-field of discrepancy theory, that deals with balancing geometric sets, such as intervals or rectangles. The general research question in this field is: given a set of ''points'' in a geometric space, and a set of ''objects'' in the same space, can we color each point in one of two different colors (e.g. black and white), such that each object contains roughly the same number of points of each color? Formally, the ''discrepancy'' of an object is defined as the difference between the number of white points and the number of black points in that object; the objective is to color the points such that the maximum discrepancy of an object is as small as possible. Intervals In the simplest geometric discrepancy setting, the set of objects is the set of all sub-intervals of the real interval ,1 In this setting, it is possible to attain discrepancy 1: simply color the points alternately black - white - black - white - etc. Then, the discrepancy of eve ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Discrepancy Theory
In mathematics, discrepancy theory describes the deviation of a situation from the state one would like it to be in. It is also called the theory of irregularities of distribution. This refers to the theme of ''classical'' discrepancy theory, namely distributing points in some space such that they are evenly distributed with respect to some (mostly geometrically defined) subsets. The discrepancy (irregularity) measures how far a given distribution deviates from an ideal one. Discrepancy theory can be described as the study of inevitable irregularities of distributions, in measure-theoretic and combinatorial settings. Just as Ramsey theory elucidates the impossibility of total disorder, discrepancy theory studies the deviations from total uniformity. A significant event in the history of discrepancy theory was the 1916 paper of Weyl on the uniform distribution of sequences in the unit interval. Theorems Discrepancy theory is based on the following classic theorems: * Geometri ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rectangle
In Euclidean geometry, Euclidean plane geometry, a rectangle is a Rectilinear polygon, rectilinear convex polygon or a quadrilateral with four right angles. It can also be defined as: an equiangular quadrilateral, since equiangular means that all of its angles are equal (360°/4 = 90°); or a parallelogram containing a right angle. A rectangle with four sides of equal length is a ''square''. The term "wikt:oblong, oblong" is used to refer to a non-square rectangle. A rectangle with Vertex (geometry), vertices ''ABCD'' would be denoted as . The word rectangle comes from the Latin ''rectangulus'', which is a combination of ''rectus'' (as an adjective, right, proper) and ''angulus'' (angle). A #Crossed rectangles, crossed rectangle is a crossed (self-intersecting) quadrilateral which consists of two opposite sides of a rectangle along with the two diagonals (therefore only two sides are parallel). It is a special case of an antiparallelogram, and its angles are not right angles an ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
With High Probability
In mathematics, an event that occurs with high probability (often shortened to w.h.p. or WHP) is one whose probability depends on a certain number ''n'' and goes to 1 as ''n'' goes to infinity, i.e. the probability of the event occurring can be made as close to 1 as desired by making ''n'' big enough. Applications The term WHP is especially used in computer science, in the analysis of probabilistic algorithms. For example, consider a certain probabilistic algorithm on a graph with ''n'' nodes. If the probability that the algorithm returns the correct answer is 1-1/n, then when the number of nodes is very large, the algorithm is correct with a probability that is very near 1. This fact is expressed shortly by saying that the algorithm is correct WHP. Some examples where this term is used are: * Miller–Rabin primality test: a probabilistic algorithm for testing whether a given number ''n'' is prime or composite. If ''n'' is composite, the test will detect ''n'' as composite WHP. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Axis-aligned Object
In geometry, an axis-aligned object (axis-parallel, axis-oriented) is an object in ''n''-dimensional space whose shape is aligned with the coordinate axes of the space. Examples are axis-aligned rectangles (or hyperrectangles), the ones with edges parallel to the coordinate axes. Minimum bounding boxes are often implicitly assumed to be axis-aligned. A more general case is rectilinear polygons, the ones with all sides parallel to coordinate axes or rectilinear polyhedra. Many problems in computational geometry allow for faster algorithms when restricted to (collections of) axis-oriented objects, such as axis-aligned rectangles or axis-aligned line segments. A different kind of example are axis-aligned ellipsoids, i.e., the ellipsoid An ellipsoid is a surface that can be obtained from a sphere by deforming it by means of directional Scaling (geometry), scalings, or more generally, of an affine transformation. An ellipsoid is a quadric surface; that is, a Surface (mathemat ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Unit Square
In mathematics, a unit square is a square whose sides have length . Often, ''the'' unit square refers specifically to the square in the Cartesian plane with corners at the four points ), , , and . Cartesian coordinates In a Cartesian coordinate system with coordinates , a unit square is defined as a square consisting of the points where both and lie in a closed unit interval from to . That is, a unit square is the Cartesian product , where denotes the closed unit interval. Complex coordinates The unit square can also be thought of as a subset of the complex plane, the topological space formed by the complex numbers. In this view, the four corners of the unit square are at the four complex numbers , , , and . Rational distance problem It is not known whether any point in the plane is a rational distance from all four vertices of the unit square. See also * Unit circle In mathematics, a unit circle is a circle of unit radius—that is, a radius of 1. Frequentl ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Online Fair Division
Online fair division is a class of fair division problems in which the resources, or the people to whom they should be allocated, or both, are not all available when the allocation decision is made. Some situations in which not all resources are available include: * Allocating food donations to charities (the "food bank" problem). Each donation must be allocated immediately when it arrives, before future donations arrive. * Allocating donated blood or organs to patients. Again, each donation must be allocated immediately, and it is not known when and what future donations will be. Some situations in which not all participants are available include: * Dividing a cake among people in a party. Some people come early and want to get a piece of cake when they arrive, but other people may come later. * Dividing the rent and rooms among tenants in a rented apartment, when one or more of them are not available during the allocation. The online nature of the problem requires different ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Convex Polytope
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others''Mathematical Programming'', by Melvyn W. Jeter (1986) p. 68/ref> (including this article) allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary. Convex polytopes play an important role both in various branches of mathematics and in applied areas, most notably in linear programming. In the influential textbooks of Grünbaum and Ziegler on the subject, as well as in many other texts in discrete geometry, convex polytopes are often simply called "polytopes". Grünbaum points out that this is solely to avoid ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Jiří Matoušek (mathematician)
Jiří (Jirka) Matoušek (10 March 1963 – 9 March 2015) was a Czech mathematician working in computational geometry and algebraic topology. He was a professor at Charles University in Prague and the author of several textbooks and research monographs. Biography Matoušek was born in Prague. In 1986, he received his Master's degree at Charles University under Miroslav Katětov. From 1986 until his death he was employed at the Department of Applied Mathematics of Charles University, holding a professor position since 2000. He was also a visiting and later full professor at ETH Zurich. In 1996, he won the European Mathematical Society prize and in 2000 he won the Scientist award of the Learned Society of the Czech Republic. In 1998 he was an Invited Speaker of the International Congress of Mathematicians in Berlin. He became a fellow of the Learned Society of the Czech Republic in 2005. Matoušek's paper on computational aspects of algebraic topology won the Best Paper award ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Primal Shatter Function
A class of sets is said to shatter another set if it is possible to "pick out" any element of that set using intersection. The concept of shattered sets plays an important role in Vapnik–Chervonenkis theory, also known as VC-theory. Shattering and VC-theory are used in the study of empirical processes as well as in statistical computational learning theory. Definition Suppose ''A'' is a set and ''C'' is a class of sets. The class ''C'' shatters the set ''A'' if for each subset ''a'' of ''A'', there is some element ''c'' of ''C'' such that : a = c \cap A. Equivalently, ''C'' shatters ''A'' when their intersection is equal to ''As power set: ''P''(''A'') = . We employ the letter ''C'' to refer to a "class" or "collection" of sets, as in a Vapnik–Chervonenkis class (VC-class). The set ''A'' is often assumed to be finite because, in empirical processes, we are interested in the shattering of finite sets of data points. Example We will show that the class of all d ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
