In discrete geometry, an isosceles set is a set of points with the property that every three of them form an isosceles triangle. More precisely, each three points should determine at most two distances; this also allows degenerate isosceles triangles formed by three equally-spaced points on a line.
The problem of finding the largest isosceles set in a Euclidean space of a given dimension was posed in 1946 by Paul Erdős. In his statement of the problem, Erdős observed that the largest such set in the Euclidean plane has six points. [1] In his 1947 solution, Leroy Milton Kelly showed more strongly that the unique six-point planar isosceles set consists of the vertices and center of a regular pentagon. In three dimensions, Kelly found an eight-point isosceles set, six points of which are the same; the remaining two points lie on a line perpendicular to the pentagon through its center, at the same distance as the pentagon vertices from the center. [2] This three-dimensional example was later proven to be optimal, and to be the unique optimal solution. [3] [4]
Kelly's eight-point three-dimensional isosceles set can be decomposed into two sets (the three points on a line perpendicular to the pentagon) and (the five vertices of the pentagon), with the property that each point in is equidistant from all points of . When such a decomposition is possible, in Euclidean spaces of any dimension, and must lie in perpendicular subspaces, must be an isosceles set within its subspace, and the set formed from by adding the point at the intersection of its two subspaces must also be an isosceles set within its subspace. In this way, an isosceles set in high dimensions can sometimes be decomposed into isosceles sets in lower dimensions. On the other hand, when an isosceles set has no decomposition of this type, then it must have a stronger property than being isosceles: it has only two distances, among all pairs of points. [5]
Despite this decomposition theorem, it is possible for the largest two-distance set and the largest isosceles set in the same dimension to have different sizes. This happens, for instance, in the plane, where the largest two-distance set has five points (the vertices of a regular pentagon), while the largest isosceles set has six points. In this case, the six-point isosceles set has a decomposition where is the singleton set of the central point (in a space of zero dimensions) and consists of all remaining points. [5]
In -dimensional space, an isosceles set can have at most
points. [5] This is tight for and for but not necessarily for other dimensions. The maximum number of points in a -dimensional isosceles set, for , is known to be [6]
but these numbers are not known for higher dimensions. [7]
Lisoněk provides the following construction of two-distance sets with
points, which also produces isosceles sets with
points. In -dimensional Euclidean space, let (for ) denote the vector a unit distance from the origin along the th coordinate axis, and construct the set consisting of all points for . Then lies in the -dimensional subspace of points with coordinate sum ; its convex hull is the hypersimplex . It has only two distances: two points formed from sums of overlapping pairs of unit vectors have distance , while two points formed from disjoint pairs of unit vectors have distance . Adding one more point to at its centroid forms a -dimensional isosceles set. For instance, for , this construction produces a suboptimal isosceles set with seven points, the vertices and center of a regular octahedron, rather than the optimal eight-point set. [6]
The same problem can also be considered for other metric spaces. For instance, for Hamming spaces, somewhat smaller upper bounds are known than for Euclidean spaces of the same dimension. [7] In an ultrametric space, the whole space (and any of its subsets) is an isosceles set. Therefore, ultrametric spaces are sometimes called isosceles spaces. However, not every isosceles set is ultrametric; for instance, obtuse Euclidean isosceles triangles are not ultrametric. [8]
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in 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 n, which are called Euclidean n-spaces when one wants to specify their dimension. For n equal to one or two, they are commonly called respectively Euclidean lines and Euclidean planes. The qualifier "Euclidean" is used to distinguish Euclidean spaces from other spaces that were later considered in physics and modern mathematics.
In mathematics, a metric space is a set together with a notion of distance between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general setting for studying many of the concepts of mathematical analysis and geometry.
In Euclidean geometry, two objects are similar if they have the same shape, or if one has the same shape as the mirror image of the other. More precisely, one can be obtained from the other by uniformly scaling, possibly with additional translation, rotation and reflection. This means that either object can be rescaled, repositioned, and reflected, so as to coincide precisely with the other object. If two objects are similar, each is congruent to the result of a particular uniform scaling of the other.
Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria. Since spatial cognition is a rich source of conceptual metaphors in human thought, the term is also frequently used metaphorically to mean a measurement of the amount of difference between two similar objects or a degree of separation. Most such notions of distance, both physical and metaphorical, are formalized in mathematics using the notion of a metric space.
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.
In mathematics, an affine space is a geometric structure that generalizes some of the properties of Euclidean spaces in such a way that these are independent of the concepts of distance and measure of angles, keeping only the properties related to parallelism and ratio of lengths for parallel line segments. Affine space is the setting for affine geometry.
In mathematics, an ultrametric space is a metric space in which the triangle inequality is strengthened to . Sometimes the associated metric is also called a non-Archimedean metric or super-metric.
In Euclidean geometry, linear separability is a property of two sets of points. This is most easily visualized in two dimensions by thinking of one set of points as being colored blue and the other set of points as being colored red. These two sets are linearly separable if there exists at least one line in the plane with all of the blue points on one side of the line and all the red points on the other side. This idea immediately generalizes to higher-dimensional Euclidean spaces if the line is replaced by a hyperplane.
In geometry, a straight line, usually abbreviated line, is an infinitely long object with no width, depth, or curvature, an idealization of such physical objects as a straightedge, a taut string, or a ray of light. Lines are spaces of dimension one, which may be embedded in spaces of dimension two, three, or higher. The word line may also refer, in everyday life, to a line segment, which is a part of a line delimited by two points.
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others 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.
In mathematics, the "happy ending problem" is the following statement:
In geometry, a three-dimensional space is a mathematical space in which three values (coordinates) are required to determine the position of a point. Most commonly, it is the three-dimensional Euclidean space, that is, the Euclidean space of dimension three, which models physical space. More general three-dimensional spaces are called 3-manifolds. The term may also refer colloquially to a subset of space, a three-dimensional region, a solid figure.
In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.
In geometry, the Beckman–Quarles theorem states that if a transformation of the Euclidean plane or a higher-dimensional Euclidean space preserves unit distances, then it preserves all Euclidean distances. Equivalently, every homomorphism from the unit distance graph of the plane to itself must be an isometry of the plane. The theorem is named after Frank S. Beckman and Donald A. Quarles Jr., who published this result in 1953; it was later rediscovered by other authors and re-proved in multiple ways. Analogous theorems for rational subsets of Euclidean spaces, or for non-Euclidean geometry, are also known.
In mathematics, a Euclidean distance matrix is an n×n matrix representing the spacing of a set of n points in Euclidean space. For points in k-dimensional space ℝk, the elements of their Euclidean distance matrix A are given by squares of distances between them. That is
In geometry, a flat or affine subspace is a subset of an affine space that is itself an affine space. In the case the parent space is Euclidean, a flat is a Euclidean subspace which inherits the notion of distance from its parent space.
In the mathematics of structural rigidity, a rigidity matroid is a matroid that describes the number of degrees of freedom of an undirected graph with rigid edges of fixed lengths, embedded into Euclidean space. In a rigidity matroid for a graph with n vertices in d-dimensional space, a set of edges that defines a subgraph with k degrees of freedom has matroid rank dn − k. A set of edges is independent if and only if, for every edge in the set, removing the edge would increase the number of degrees of freedom of the remaining subgraph.
In mathematics, and particularly in graph theory, the dimension of a graph is the least integer n such that there exists a "classical representation" of the graph in the Euclidean space of dimension n with all the edges having unit length.
In discrete and computational geometry, a set of points in the Euclidean plane or a higher-dimensional Euclidean space is said to be in convex position or convex independent if none of the points can be represented as a convex combination of the others. A finite set of points is in convex position if all of the points are vertices of their convex hull. More generally, a family of convex sets is said to be in convex position if they are pairwise disjoint and none of them is contained in the convex hull of the others.
In geometry, the distance set of a collection of points is the set of distances between distinct pairs of points. Thus, it can be seen as the generalization of a difference set, the set of distances in collections of numbers.
