- Source: Incidence (geometry)
- Source: Incidence geometry
In geometry, an incidence relation is a heterogeneous relation that captures the idea being expressed when phrases such as "a point lies on a line" or "a line is contained in a plane" are used. The most basic incidence relation is that between a point, P, and a line, l, sometimes denoted P I l. If P and l are incident, P I l, the pair (P, l) is called a flag.
There are many expressions used in common language to describe incidence (for example, a line passes through a point, a point lies in a plane, etc.) but the term "incidence" is preferred because it does not have the additional connotations that these other terms have, and it can be used in a symmetric manner. Statements such as "line l1 intersects line l2" are also statements about incidence relations, but in this case, it is because this is a shorthand way of saying that "there exists a point P that is incident with both line l1 and line l2". When one type of object can be thought of as a set of the other type of object (viz., a plane is a set of points) then an incidence relation may be viewed as containment.
Statements such as "any two lines in a plane meet" are called incidence propositions. This particular statement is true in a projective plane, though not true in the Euclidean plane where lines may be parallel. Historically, projective geometry was developed in order to make the propositions of incidence true without exceptions, such as those caused by the existence of parallels. From the point of view of synthetic geometry, projective geometry should be developed using such propositions as axioms. This is most significant for projective planes due to the universal validity of Desargues' theorem in higher dimensions.
In contrast, the analytic approach is to define projective space based on linear algebra and utilizing homogeneous co-ordinates. The propositions of incidence are derived from the following basic result on vector spaces: given subspaces U and W of a (finite-dimensional) vector space V, the dimension of their intersection is dim U + dim W − dim (U + W). Bearing in mind that the geometric dimension of the projective space P(V) associated to V is dim V − 1 and that the geometric dimension of any subspace is positive, the basic proposition of incidence in this setting can take the form: linear subspaces L and M of projective space P meet provided dim L + dim M ≥ dim P.
The following sections are limited to projective planes defined over fields, often denoted by PG(2, F), where F is a field, or P2F. However these computations can be naturally extended to higher-dimensional projective spaces, and the field may be replaced by a division ring (or skewfield) provided that one pays attention to the fact that multiplication is not commutative in that case.
PG(2,F)
Let V be the three-dimensional vector space defined over the field F. The projective plane P(V) = PG(2, F) consists of the one-dimensional vector subspaces of V, called points, and the two-dimensional vector subspaces of V, called lines. Incidence of a point and a line is given by containment of the one-dimensional subspace in the two-dimensional subspace.
Fix a basis for V so that we may describe its vectors as coordinate triples (with respect to that basis). A one-dimensional vector subspace consists of a non-zero vector and all of its scalar multiples. The non-zero scalar multiples, written as coordinate triples, are the homogeneous coordinates of the given point, called point coordinates. With respect to this basis, the solution space of a single linear equation {(x, y, z) | ax + by + cz = 0} is a two-dimensional subspace of V, and hence a line of P(V). This line may be denoted by line coordinates [a, b, c], which are also homogeneous coordinates since non-zero scalar multiples would give the same line. Other notations are also widely used. Point coordinates may be written as column vectors, (x, y, z)T, with colons, (x : y : z), or with a subscript, (x, y, z)P. Correspondingly, line coordinates may be written as row vectors, (a, b, c), with colons, [a : b : c] or with a subscript, (a, b, c)L. Other variations are also possible.
Incidence expressed algebraically
Given a point P = (x, y, z) and a line l = [a, b, c], written in terms of point and line coordinates, the point is incident with the line (often written as P I l), if and only if,
ax + by + cz = 0.
This can be expressed in other notations as:
a
x
+
b
y
+
c
z
=
[
a
,
b
,
c
]
⋅
(
x
,
y
,
z
)
=
(
a
,
b
,
c
)
L
⋅
(
x
,
y
,
z
)
P
=
{\displaystyle ax+by+cz=[a,b,c]\cdot (x,y,z)=(a,b,c)_{L}\cdot (x,y,z)_{P}=}
=
[
a
:
b
:
c
]
⋅
(
x
:
y
:
z
)
=
(
a
,
b
,
c
)
(
x
y
z
)
=
0.
{\displaystyle =[a:b:c]\cdot (x:y:z)=(a,b,c)\left({\begin{matrix}x\\y\\z\end{matrix}}\right)=0.}
No matter what notation is employed, when the homogeneous coordinates of the point and line are just considered as ordered triples, their incidence is expressed as having their dot product equal 0.
The line incident with a pair of distinct points
Let P1 and P2 be a pair of distinct points with homogeneous coordinates (x1, y1, z1) and (x2, y2, z2) respectively. These points determine a unique line l with an equation of the form ax + by + cz = 0 and must satisfy the equations:
ax1 + by1 + cz1 = 0 and
ax2 + by2 + cz2 = 0.
In matrix form this system of simultaneous linear equations can be expressed as:
(
x
y
z
x
1
y
1
z
1
x
2
y
2
z
2
)
(
a
b
c
)
=
(
0
0
0
)
.
{\displaystyle \left({\begin{matrix}x&y&z\\x_{1}&y_{1}&z_{1}\\x_{2}&y_{2}&z_{2}\end{matrix}}\right)\left({\begin{matrix}a\\b\\c\end{matrix}}\right)=\left({\begin{matrix}0\\0\\0\end{matrix}}\right).}
This system has a nontrivial solution if and only if the determinant,
|
x
y
z
x
1
y
1
z
1
x
2
y
2
z
2
|
=
0.
{\displaystyle \left|{\begin{matrix}x&y&z\\x_{1}&y_{1}&z_{1}\\x_{2}&y_{2}&z_{2}\end{matrix}}\right|=0.}
Expansion of this determinantal equation produces a homogeneous linear equation, which must be the equation of line l. Therefore, up to a common non-zero constant factor we have l = [a, b, c] where:
a = y1z2 - y2z1,
b = x2z1 - x1z2, and
c = x1y2 - x2y1.
In terms of the scalar triple product notation for vectors, the equation of this line may be written as:
P ⋅ P1 × P2 = 0,
where P = (x, y, z) is a generic point.
= Collinearity
=Points that are incident with the same line are said to be collinear. The set of all points incident with the same line is called a range.
If P1 = (x1, y1, z1), P2 = (x2, y2, z2), and P3 = (x3, y3, z3), then these points are collinear if and only if
|
x
1
y
1
z
1
x
2
y
2
z
2
x
3
y
3
z
3
|
=
0
,
{\displaystyle \left|{\begin{matrix}x_{1}&y_{1}&z_{1}\\x_{2}&y_{2}&z_{2}\\x_{3}&y_{3}&z_{3}\end{matrix}}\right|=0,}
i.e., if and only if the determinant of the homogeneous coordinates of the points is equal to zero.
Intersection of a pair of lines
Let l1 = [a1, b1, c1] and l2 = [a2, b2, c2] be a pair of distinct lines. Then the intersection of lines l1 and l2 is point a P = (x0, y0, z0) that is the simultaneous solution (up to a scalar factor) of the system of linear equations:
a1x + b1y + c1z = 0 and
a2x + b2y + c2z = 0.
The solution of this system gives:
x0 = b1c2 - b2c1,
y0 = a2c1 - a1c2, and
z0 = a1b2 - a2b1.
Alternatively, consider another line l = [a, b, c] passing through the point P, that is, the homogeneous coordinates of P satisfy the equation:
ax+ by + cz = 0.
Combining this equation with the two that define P, we can seek a non-trivial solution of the matrix equation:
(
a
b
c
a
1
b
1
c
1
a
2
b
2
c
2
)
(
x
y
z
)
=
(
0
0
0
)
.
{\displaystyle \left({\begin{matrix}a&b&c\\a_{1}&b_{1}&c_{1}\\a_{2}&b_{2}&c_{2}\end{matrix}}\right)\left({\begin{matrix}x\\y\\z\end{matrix}}\right)=\left({\begin{matrix}0\\0\\0\end{matrix}}\right).}
Such a solution exists provided the determinant,
|
a
b
c
a
1
b
1
c
1
a
2
b
2
c
2
|
=
0.
{\displaystyle \left|{\begin{matrix}a&b&c\\a_{1}&b_{1}&c_{1}\\a_{2}&b_{2}&c_{2}\end{matrix}}\right|=0.}
The coefficients of a, b and c in this equation give the homogeneous coordinates of P.
The equation of the generic line passing through the point P in scalar triple product notation is:
l ⋅ l1 × l2 = 0.
= Concurrence
=Lines that meet at the same point are said to be concurrent. The set of all lines in a plane incident with the same point is called a pencil of lines centered at that point. The computation of the intersection of two lines shows that the entire pencil of lines centered at a point is determined by any two of the lines that intersect at that point. It immediately follows that the algebraic condition for three lines, [a1, b1, c1], [a2, b2, c2], [a3, b3, c3] to be concurrent is that the determinant,
|
a
1
b
1
c
1
a
2
b
2
c
2
a
3
b
3
c
3
|
=
0.
{\displaystyle \left|{\begin{matrix}a_{1}&b_{1}&c_{1}\\a_{2}&b_{2}&c_{2}\\a_{3}&b_{3}&c_{3}\end{matrix}}\right|=0.}
See also
Menelaus theorem
Ceva's theorem
Concyclic
Hopcroft's problem of finding point–line incidences
Incidence matrix
Incidence algebra
Incidence structure
Incidence geometry
Levi graph
Hilbert's axioms
References
Harold L. Dorwart (1966) The Geometry of Incidence, Prentice Hall.
In mathematics, incidence geometry is the study of incidence structures. A geometric structure such as the Euclidean plane is a complicated object that involves concepts such as length, angles, continuity, betweenness, and incidence. An incidence structure is what is obtained when all other concepts are removed and all that remains is the data about which points lie on which lines. Even with this severe limitation, theorems can be proved and interesting facts emerge concerning this structure. Such fundamental results remain valid when additional concepts are added to form a richer geometry. It sometimes happens that authors blur the distinction between a study and the objects of that study, so it is not surprising to find that some authors refer to incidence structures as incidence geometries.
Incidence structures arise naturally and have been studied in various areas of mathematics. Consequently, there are different terminologies to describe these objects. In graph theory they are called hypergraphs, and in combinatorial design theory they are called block designs. Besides the difference in terminology, each area approaches the subject differently and is interested in questions about these objects relevant to that discipline. Using geometric language, as is done in incidence geometry, shapes the topics and examples that are normally presented. It is, however, possible to translate the results from one discipline into the terminology of another, but this often leads to awkward and convoluted statements that do not appear to be natural outgrowths of the topics. In the examples selected for this article we use only those with a natural geometric flavor.
A special case that has generated much interest deals with finite sets of points in the Euclidean plane and what can be said about the number and types of (straight) lines they determine. Some results of this situation can extend to more general settings since only incidence properties are considered.
Incidence structures
An incidence structure (P, L, I) consists of a set P whose elements are called points, a disjoint set L whose elements are called lines and an incidence relation I between them, that is, a subset of P × L whose elements are called flags. If (A, l) is a flag, we say that A is incident with l or that l is incident with A (the terminology is symmetric), and write A I l. Intuitively, a point and line are in this relation if and only if the point is on the line. Given a point B and a line m which do not form a flag, that is, the point is not on the line, the pair (B, m) is called an anti-flag.
= Distance in an incidence structure
=There is no natural concept of distance (a metric) in an incidence structure. However, a combinatorial metric does exist in the corresponding incidence graph (Levi graph), namely the length of the shortest path between two vertices in this bipartite graph. The distance between two objects of an incidence structure – two points, two lines or a point and a line – can be defined to be the distance between the corresponding vertices in the incidence graph of the incidence structure.
Another way to define a distance again uses a graph-theoretic notion in a related structure, this time the collinearity graph of the incidence structure. The vertices of the collinearity graph are the points of the incidence structure and two points are joined if there exists a line incident with both points. The distance between two points of the incidence structure can then be defined as their distance in the collinearity graph.
When distance is considered in an incidence structure, it is necessary to mention how it is being defined.
Partial linear spaces
Incidence structures that are most studied are those that satisfy some additional properties (axioms), such as projective planes, affine planes, generalized polygons, partial geometries and near polygons. Very general incidence structures can be obtained by imposing "mild" conditions, such as:
A partial linear space is an incidence structure for which the following axioms are true:
Every pair of distinct points determines at most one line.
Every line contains at least two distinct points.
In a partial linear space it is also true that every pair of distinct lines meet in at most one point. This statement does not have to be assumed as it is readily proved from axiom one above.
Further constraints are provided by the regularity conditions:
RLk: Each line is incident with the same number of points. If finite this number is often denoted by k.
RPr: Each point is incident with the same number of lines. If finite this number is often denoted by r.
The second axiom of a partial linear space implies that k > 1. Neither regularity condition implies the other, so it has to be assumed that r > 1.
A finite partial linear space satisfying both regularity conditions with k, r > 1 is called a tactical configuration. Some authors refer to these simply as configurations, or projective configurations. If a tactical configuration has n points and m lines, then, by double counting the flags, the relationship nr = mk is established. A common notation refers to (nr, mk)-configurations. In the special case where n = m (and hence, r = k) the notation (nk, nk) is often simply written as (nk).
A linear space is a partial linear space such that:
Every pair of distinct points determines exactly one line.
Some authors add a "non-degeneracy" (or "non-triviality") axiom to the definition of a (partial) linear space, such as:
There exist at least two distinct lines.
This is used to rule out some very small examples (mainly when the sets P or L have fewer than two elements) that would normally be exceptions to general statements made about the incidence structures. An alternative to adding the axiom is to refer to incidence structures that do not satisfy the axiom as being trivial and those that do as non-trivial.
Each non-trivial linear space contains at least three points and three lines, so the simplest non-trivial linear space that can exist is a triangle.
A linear space having at least three points on every line is a Sylvester–Gallai design.
Fundamental geometric examples
Some of the basic concepts and terminology arises from geometric examples, particularly projective planes and affine planes.
= Projective planes
=A projective plane is a linear space in which:
Every pair of distinct lines meet in exactly one point,
and that satisfies the non-degeneracy condition:
There exist four points, no three of which are collinear.
There is a bijection between P and L in a projective plane. If P is a finite set, the projective plane is referred to as a finite projective plane. The order of a finite projective plane is n = k – 1, that is, one less than the number of points on a line. All known projective planes have orders that are prime powers. A projective plane of order n is an ((n2 + n + 1)n + 1) configuration.
The smallest projective plane has order two and is known as the Fano plane.
Fano plane
This famous incidence geometry was developed by the Italian mathematician Gino Fano. In his work on proving the independence of the set of axioms for projective n-space that he developed, he produced a finite three-dimensional space with 15 points, 35 lines and 15 planes, in which each line had only three points on it. The planes in this space consisted of seven points and seven lines and are now known as Fano planes.
The Fano plane cannot be represented in the Euclidean plane using only points and straight line segments (i.e., it is not realizable). This is a consequence of the Sylvester–Gallai theorem, according to which every realizable incidence geometry must include an ordinary line, a line containing only two points. The Fano plane has no such line (that is, it is a Sylvester–Gallai configuration), so it is not realizable.
A complete quadrangle consists of four points, no three of which are collinear. In the Fano plane, the three points not on a complete quadrangle are the diagonal points of that quadrangle and are collinear. This contradicts the Fano axiom, often used as an axiom for the Euclidean plane, which states that the three diagonal points of a complete quadrangle are never collinear.
= Affine planes
=An affine plane is a linear space satisfying:
For any point A and line l not incident with it (an anti-flag) there is exactly one line m incident with A (that is, A I m), that does not meet l (known as Playfair's axiom),
and satisfying the non-degeneracy condition:
There exists a triangle, i.e. three non-collinear points.
The lines l and m in the statement of Playfair's axiom are said to be parallel. Every affine plane can be uniquely extended to a projective plane. The order of a finite affine plane is k, the number of points on a line. An affine plane of order n is an ((n2)n + 1, (n2 + n)n) configuration.
Hesse configuration
The affine plane of order three is a (94, 123) configuration. When embedded in some ambient space it is called the Hesse configuration. It is not realizable in the Euclidean plane but is realizable in the complex projective plane as the nine inflection points of an elliptic curve with the 12 lines incident with triples of these.
The 12 lines can be partitioned into four classes of three lines apiece where, in each class the lines are mutually disjoint. These classes are called parallel classes of lines. Adding four new points, each being added to all the lines of a single parallel class (so all of these lines now intersect), and one new line containing just these four new points produces the projective plane of order three, a (134) configuration. Conversely, starting with the projective plane of order three (it is unique) and removing any single line and all the points on that line produces this affine plane of order three (it is also unique).
Removing one point and the four lines that pass through that point (but not the other points on them) produces the (83) Möbius–Kantor configuration.
Partial geometries
Given an integer α ≥ 1, a tactical configuration satisfying:
For every anti-flag (B, m) there are α flags (A, l) such that B I l and A I m,
is called a partial geometry. If there are s + 1 points on a line and t + 1 lines through a point, the notation for a partial geometry is pg(s, t, α).
If α = 1 these partial geometries are generalized quadrangles.
If α = s + 1 these are called Steiner systems.
Generalized polygons
For n > 2, a generalized n-gon is a partial linear space whose incidence graph Γ has the property:
The girth of Γ (length of the shortest cycle) is twice the diameter of Γ (the largest distance between two vertices, n in this case).
A generalized 2-gon is an incidence structure, which is not a partial linear space, consisting of at least two points and two lines with every point being incident with every line. The incidence graph of a generalized 2-gon is a complete bipartite graph.
A generalized n-gon contains no ordinary m-gon for 2 ≤ m < n and for every pair of objects (two points, two lines or a point and a line) there is an ordinary n-gon that contains them both.
Generalized 3-gons are projective planes. Generalized 4-gons are called generalized quadrangles. By the Feit-Higman theorem the only finite generalized n-gons with at least three points per line and three lines per point have n = 2, 3, 4, 6 or 8.
Near polygons
For a non-negative integer d a near 2d-gon is an incidence structure such that:
The maximum distance (as measured in the collinearity graph) between two points is d, and
For every point X and line l there is a unique point on l that is closest to X.
A near 0-gon is a point, while a near 2-gon is a line. The collinearity graph of a near 2-gon is a complete graph. A near 4-gon is a generalized quadrangle (possibly degenerate). Every finite generalized polygon except the projective planes is a near polygon. Any connected bipartite graph is a near polygon and any near polygon with precisely two points per line is a connected bipartite graph. Also, all dual polar spaces are near polygons.
Many near polygons are related to finite simple groups like the Mathieu groups and the Janko group J2. Moreover, the generalized 2d-gons, which are related to Groups of Lie type, are special cases of near 2d-gons.
Möbius planes
An abstract Möbius plane (or inversive plane) is an incidence structure where, to avoid possible confusion with the terminology of the classical case, the lines are referred to as cycles or blocks.
Specifically, a Möbius plane is an incidence structure of points and cycles such that:
Every triple of distinct points is incident with precisely one cycle.
For any flag (P, z) and any point Q not incident with z there is a unique cycle z∗ with P I z∗, Q I z∗ and z ∩ z∗ = {P}. (The cycles are said to touch at P.)
Every cycle has at least three points and there exists at least one cycle.
The incidence structure obtained at any point P of a Möbius plane by taking as points all the points other than P and as lines only those cycles that contain P (with P removed), is an affine plane. This structure is called the residual at P in design theory.
A finite Möbius plane of order m is a tactical configuration with k = m + 1 points per cycle that is a 3-design, specifically a 3-(m2 + 1, m + 1, 1) block design.
Incidence theorems in the Euclidean plane
= The Sylvester-Gallai theorem
=A question raised by J.J. Sylvester in 1893 and finally settled by Tibor Gallai concerned incidences of a finite set of points in the Euclidean plane.
Theorem (Sylvester-Gallai): A finite set of points in the Euclidean plane is either collinear or there exists a line incident with exactly two of the points.
A line containing exactly two of the points is called an ordinary line in this context. Sylvester was probably led to the question while pondering about the embeddability of the Hesse configuration.
= The de Bruijn–Erdős theorem
=A related result is the de Bruijn–Erdős theorem. Nicolaas Govert de Bruijn and Paul Erdős proved the result in the more general setting of projective planes, but it still holds in the Euclidean plane. The theorem is:
In a projective plane, every non-collinear set of n points determines at least n distinct lines.
As the authors pointed out, since their proof was combinatorial, the result holds in a larger setting, in fact in any incidence geometry in which there is a unique line through every pair of distinct points. They also mention that the Euclidean plane version can be proved from the Sylvester-Gallai theorem using induction.
= The Szemerédi–Trotter theorem
=A bound on the number of flags determined by a finite set of points and the lines they determine is given by:
Theorem (Szemerédi–Trotter): given n points and m lines in the plane, the number of flags (incident point-line pairs) is:
O
(
n
2
3
m
2
3
+
n
+
m
)
,
{\displaystyle O\left(n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m\right),}
and this bound cannot be improved, except in terms of the implicit constants.
This result can be used to prove Beck's theorem.
A similar bound for the number of incidences is conjectured for point-circle incidences, but only weaker upper bounds are known.
= Beck's theorem
=Beck's theorem says that finite collections of points in the plane fall into one of two extremes; one where a large fraction of points lie on a single line, and one where a large number of lines are needed to connect all the points.
The theorem asserts the existence of positive constants C, K such that given any n points in the plane, at least one of the following statements is true:
There is a line that contains at least n/C of the points.
There exist at least n2/K lines, each of which contains at least two of the points.
In Beck's original argument, C is 100 and K is an unspecified constant; it is not known what the optimal values of C and K are.
More examples
Projective geometries
Moufang polygon
Schläfli double six
Reye configuration
Cremona–Richmond configuration
Kummer configuration
Klein configuration
Non-Desarguesian planes
See also
Combinatorial designs
Finite geometry
Intersection theorem
Levi graph
Notes
References
Aigner, Martin; Ziegler, Günter M. (2010), "Lines in the plane and decompositions of graphs", Proofs from The Book, Springer, pp. 63–67, doi:10.1007/978-3-642-00856-6_10, ISBN 978-3-642-00855-9
Batten, Lynn Margaret (1986), Combinatorics of Finite Geometries, Cambridge University Press, ISBN 978-0-521-31857-0
Batten, Lynn Margaret; Beutelspacher, Albrecht (1993), The Theory of Finite Linear Spaces, Cambridge University Press, ISBN 978-0-521-33317-7
Buekenhout, Francis (1995), Handbook of Incidence Geometry: Buildings and Foundations, Elsevier, ISBN 978-0-444-88355-1
Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 978-1-58488-506-1
Collino, Alberto; Conte, Alberto; Verra, Alessandro (2013). "On the life and scientific work of Gino Fano". arXiv:1311.7177 [math.HO].
De Bruyn, Bart (2016), An Introduction to Incidence Geometry, Frontiers in Mathematics, Springer International Publishing, doi:10.1007/978-3-319-43811-5, ISBN 978-3-319-43810-8
Dembowski, Peter (1968), Finite geometries, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 44, Berlin, New York: Springer-Verlag, ISBN 978-3-540-61786-0, MR 0233275
Malkevitch, Joe. "Finite Geometries?". Retrieved Dec 2, 2013.
Moorhouse, G. Eric. "Incidence Geometry" (PDF). Archived from the original (PDF) on October 29, 2013. Retrieved Oct 20, 2012.
Ueberberg, Johannes (2011), Foundations of Incidence Geometry, Springer Monographs in Mathematics, Springer, doi:10.1007/978-3-642-20972-7, ISBN 978-3-642-26960-8.
Shult, Ernest E. (2011), Points and Lines, Universitext, Springer, doi:10.1007/978-3-642-15627-4, ISBN 978-3-642-15626-7.
Ball, Simeon (2015), Finite Geometry and Combinatorial Applications, London Mathematical Society Student Texts, Cambridge University Press, ISBN 978-1107518438.
External links
Media related to Incidence geometry at Wikimedia Commons
incidence system at the Encyclopedia of Mathematics
Kata Kunci Pencarian:
- Titik (geometri)
- Geometri hingga
- Geometri diskrit
- Geometri mutlak
- Incidence (geometry)
- Incidence geometry
- Affine plane (incidence geometry)
- Incidence structure
- Synthetic geometry
- Incidence
- Projective geometry
- Absolute geometry
- Point (geometry)
- Geometry
