Points, Lines, and Incidences

To honor Mathematics and Statistics Awareness Month, I will treat some remarkable developments concerning a basic intuitive idea in geometry concerning points and lines. …

Joseph Malkevitch
York College (CUNY

Introduction

When people think about mathematics they think of numbers and shapes. Numbers covers the interest of mathematics in arithmetic and algebra. And shape relates to mathematics’ concern with geometry. However, in many ways a better way to capture the essence of mathematics is to say that it is concerned with understanding patterns of all kinds, whether they be numerical or geometrical patterns or patterns in more general senses.

To honor Mathematics and Statistics Awareness Month, I will treat some remarkable developments concerning a basic intuitive idea in geometry concerning points and lines. For our discussion I will be concerned with points, lines and segments (portions of lines between two points) that are drawn in the Euclidean plane in contrast to points and lines on another surface such as a sphere or ellipsoid or in the hyperbolic (many parallel lines) or projective planes (no parallel lines). Many of these ideas have ancient roots in many cultures, but often mathematics reinvents itself by trying to understand ideas that at first glance might seem to have been resolved in the distant past.

Configurations of points and lines

Consider the diagram in Figure 1 that shows two triangles being viewed by an eye. While this diagram has infinitely many points on the lines, we will only be interested in the points accentuated with dots. In this diagram there are many segments but some of these lie along the same line. In drawings of this kind we can show only a part of a line. Note that the corresponding vertices of the triangles determine three lines: AA’, BB’ and CC’ that meet at the point called Eye. Note also that we will consider EyeA’, EyeA and AA’ as three different segments even though EyeA’ is made up of two smaller (shorter) segments.

If you count the number of points in Figure 1, there are 7 and the number of lines is 9. Three of the lines have three points on them and the other 6 lines have two points on them. Note that while the segment EyeC and the segment AB meet at a point, we will not be concerned with that point or the one where segment A’B’ meets segment CC’. We need to decide how to report the information we see. The segment EyeA’ consists of the segments EyeA and AA’ which make up the longer segment but the points Eye, A and A’ all are points on one line.

The set of labeled points shown in Figure 1 accounts for some two-point lines and some of the points lie on 3-point lines, but note that the diagram does not show all of the lines that the points in the set of points (7 points) might determine. If 7 points were in “general position” they would determine 21 (= (7*6)/2 ) different lines. You are probably aware that any two distinct points in the Euclidean plane determine a unique line. However, if one starts, for example, with 4 points on a line, then any pair of these points determines the same line.

Figure 1 is the starting point for a famous theorem that I will return to in a moment, but to set the stage for what is to come let us also look at the points and lines in Figure 2. This diagram calls attention to 7 points also, but with only 3 lines. One line has 2 points, another 3 points and the third line has 4 points. Five points are shown with only a single line passing through those points and two points have two lines which pass through them. However, perhaps you are wondering if the two “vertical” lines actually intersect (meet) somewhere in the distance. Many people would say the diagram suggests that the lines are parallel, that is, that they do not have a point in common.

Figure 2 (A collection of 7 points and three lines.)

Though in many ways the result I am about to discuss belongs more naturally to projective geometry (where there are no parallel lines, all pairs of distinct lines meet in exactly one point) than Euclidean geometry, it is a theorem as stated for the Euclidean plane.

There is much more that can be said about the diagram that we started with in Figure 1. Figure 3 shows another diagram that helps illustrate the mathematical result involved. The point labeled “Eye” in Figure 1 corresponds to the point labeled O in Figure 2. Furthermore the two triangles in Figure 1 did not overlap but they do in Figure 2. What happens (Figure 3) when we look at the lines determined by the corresponding vertices of the two triangles, the lines determined by AA’, by BB’ and by CC’? Of course it might be possible that some pair of these three lines would be parallel and would not meet. However, let us assume that in fact every pair of these lines do intersect, and they intersect in the points P, Q and R. (P and Q are shown in Figure 2 but not R.) Can anything be said about this triple of points? Ordinarily if one picks three points at “random,” one would not expect them to lie on a line but one would expect them to be the vertices of a triangle. However, the remarkable fact here is that when the two initial triangles have the property that the lines connecting their corresponding vertices meet at a point, the corresponding edges of the triangles (when no pair is parallel) meet at points which lie on a single line!!

This theorem was not noticed by the great Greek geometers but was discovered by Girard Desargues (1591-1661). It is an example of a situation in mathematics where something that one would not expect to happen, as if by magic, does happen. This ability of mathematics to make surprising connections in unexpected situations is part of what attracts so many people to the subject. For those not sure that Figure 3 might just be an accident, you can take a look at another copy of a Desargues configuration (Figure 4) highlighting the two triangles in color and–indicated in red–the point that they are in “perspective” (where the blue lines intersect), and the line that they are in “perspective” from.

Here is one formal statement of Desargues’s Theorem:

If the corresponding vertices of two distinct triangles in the Euclidean plane ABC and abc pass through a single point O then the corresponding sides of these triangles intersect at points which lie on a single line.

Sometimes this theorem is stated that if two triangles are “in perspective” from a point they are “in perspective” from a line.

Theorems like Desargues’s Theorem have come to be known as configuration theorems; there are other theorems of this kind that predate Desargues.

In addition to the “configuration” consisting of points and lines that is represented by the 10 points and 10 lines implicit in Figure 4, there is another amazing configuration theorem which is due to the great mathematician Pappus of Alexandria (lived approximately 290-350).

Pappus’s Theorem can be stated that given six points, A, B, C on one line and a, b, c on another line which intersect (none of the points being where the two lines intersect) (as shown in Figure 5) then the three points where Ab intersects aB, Ac intersects aC and Bc intersects bC are collinear (lie on a single line)!

Whereas Desargues’s Theorem can be thought of as 10 points and 10 lines with 3 points on a line and 3 lines passing through a point, the Pappus configuration can be thought of as having 9 points and 9 lines where three points lie on each of the specified lines and triples of lines pass through the specified points.

Pappus’s Theorem can be considered as a special case of another remarkable configuration theorem that was discovered by Blaise Pascal (1623-1662), the French philosopher, author and mathematician.

Pappus’s Theorem involves 6 points which lie on two lines and the way these points determine lines that create points which lie on a line as well. But since two lines are both equations of degree 1 (equations of the form $ax + by + c = 0$ where $a, b,$ and $c$ are real numbers, with both of $a$ and $b$ not zero), if we multiply these two equations together we get an equation which is of degree two in the variables $x$ and $y$. This would be a quadratic equation in two variables. The “shapes” you are probably most familiar with that satisfy such equations are the conic sections: circles, ellipses, parabolas, and hyperbolas. But two intersecting straight lines or two parallel straight lines can be thought of as “degenerate” conic sections. (A conic section gets its name because it can be thought of as what results from cutting a cone with a plane.) What Pascal realized was that one could generalize Pappus’s Theorem to planar conics.

Pascal’s Theorem:

Given 6 points which form a hexagon whose vertices lie on a conic section, then the three pairs of opposite sides of this hexagon meet at points which lie on a straight line.

The rise of interest in configuration theorems such as those of Pappus, Desargues, and Pascal were related to attempts to put an understanding of geometry in a richer context. Attempts to show that Euclid’s 5th Postulate, in a modern formulation:

If p is a point not on line l then there is a unique parallel to line l though point P

could be deduced from the other axioms (starting assumptions) were not successful. We know today why they weren’t: there are mathematically (logically consistent) geometries where Euclid’s 5th postulate fails to hold. Furthermore, people were investigating point/line questions on the sphere, a curved surface rather than a flat one, but where there were “natural” suggestions for what might be “lines” and points on such a surface. In the end, spherical geometry evolved into two different approaches. In the more interesting approach a point was considered to be a pair of points which were at opposite ends of a diameter. It may seem strange to think of two things being identified so that they are considered one, but this point of view is very fruitful because now “two points” determine a unique line, a great circle of the sphere, which is a circle centered at the center of the sphere.

Many people who know some geometry are puzzled by the difference between longitude lines and latitude lines. Longitude lines are great circles which cut through the idealized sphere that represents the Earth at the south and north poles. The circle that is “halfway” between the poles, lying in a plane perpendicular to the line joining the poles, is a great circle too, and it is the equator of the system. But all the other latitude lines that are “parallel” to the equator (in the sense that they don’t meet the equator) are not great circles. They are circles which represent the intersection of a plane parallel to the equator, with the sphere.

Incidences

Suppose we are given a “configuration” C of points and lines in the Euclidean plane; we have a finite set P containing $m$ points in the Euclidean plane and a finite set L of $n$ lines which contain some of the points of P. It is possible that the lines of L intersect at points not in P (see Figure 8) and it is possible that L does not contain all of the lines determined by pairs of points in P (Figure 2). One might be interested in counting how many point-line pairs there are in the configuration C. A point-line pair, a point $p$ of set S which is on line $l$ of L is called an incidence. We are not concerned with lengths of segments or with angles between the lines.

The point-line configuration in Figure 8 has 7 straight lines (so set L has 7 elements) and 5 points (so set P has 5 elements). Note that the lines are displayed to suggest they are infinite. The section between two points will be referred to as a segment and when we have in mind the “whole” line that a segment lies in we will call that a line. Some pairs of the points shown do not lie on any line of L. One might consider adding lines between points not already joined, and adding to our configurations points that are obtained from the intersection of such a line with an existing line (assuming that it meets an existing line in a point that is not already in S). However, in what follows we are only concerned with the points and lines in the set of points P given to us and the set of lines L given to us. For Figure 8, of the 5 points (dark dots), one has 2 lines going through it, three points have 3 lines going through them, and one point has 4 lines going through it. For the lines, 6 lines have two points on them and one line has 3 points on it.

For practice you may want by direct count to verify that this configuration has 15 point-line incidences and 10 different segments. (The line with three points has 3 segments in all.) You can count the number of points, lines, segments, number of lines with s points and number of points through which t lines pass and incidences you see in Figure 8. You should find 15 incidences, and notice you can count these by concentrating on each line in turn and finding how many points there are on each of the lines or by concentrating on the point and seeing how many lines pass through each of the points! Given the diagram shown in Figure 2 where we have 5 points in the set P and 3 lines in the set L, we can count 9 incidences in this diagram.

Shortly we will discuss a remarkable theorem about counting incidences–the Szemerédi-Trotter Theorem ). But to fully appreciate the circle of ideas involved in this result I will discuss some ideas that seem initially not related to incidences. When most people hear the word graph they think of the graph of a function. When Descartes extended the “synthetic” geometry of Euclid to the analytical geometry of today, it became possible to graph algebraic expressions. Historically this helped with the rapid and fruitful development of the Calculus.

However, there is another more recent use of the word graph. It belongs to the domain of discrete mathematics rather than the domain of continuous mathematics and involves the geometric structures consisting of dots and lines or dots and curves. Graphs of this kind consist of a number of points called vertices (singular vertex) and lines/curves which join up pairs of vertices which are called edges. Figure 9 shows a sample of some graphs.

Each of these three graphs consists of a single piece, and such a graph is called connected–intuitively there is a way of taking any pair of vertices in the graph and getting between them by moving along the edges of the graph. In principle we might have many different lines/curves which connect up a pair of vertices, and we might have vertices that are joined to themselves by a curve (or broken line) but these structures, sometimes called multi-graphs, pseudographs, or graphs with loops and multiple edges will not be considered here. Some graphs have the property that they have been drawn in the plane so that edges meet only at vertices. Such graphs are called plane graphs, and graphs which have the potential to be drawn in the plane so that edges meet only at vertices are known as planar graphs. Figure 10 shows an example of a planar graph on the left and a structurally equivalent graph, an isomorphic graph, on the right; the single crossing has been eliminated.

While graph theory is a relatively recent subarea of geometry, a relatively recent subarea of graph theory, with mathematical and computer science implications, has been the subject of graph drawing. This domain of ideas concerns questions about the nature of the appearance of different ways a graph might be drawn in the plane.

When a graph is drawn in the plane there may be many different drawings to represent isomorphic copies of the same graph. In particular one might ask for a drawing with the minimum number of crossings for that graph. This number is called the crossing number of the graph. In fact, the crossing number in itself has interesting variants because there can be a difference in the number of crossings when all of the edges are drawn with straight lines versus the number of crossings when the edges are allowed to be curves.

The Szemerédi-Trotter Theorem

A remarkable accomplishment in understanding the behavior of counting the number of incidences for a collection of points and lines was achieved by what has come to be called the Szemerédi-Trotter Theorem. This result is named after William Tom Trotter and Endre Szemerédi.

We will first set the stage for the remarkable result of Szemerédi and Trotter, which was proved in 1983.

Szemerédi-Trotter Theorem:

Suppose that we have a collection (set) of points P with m distinct points and a collection of distinct lines L with n lines in the Euclidean plane. As we saw above we will call an incidence a point-line pair (p,l) where p belongs to P and l belongs to L and point p lies on line l. Such pairs are called incidences. What is the maximum number of possible incidences, calculated in terms of the values of m and n? If we denote by I(P,L) the number of incidences for the particular given sets P and L, then we will denote by I(m,n) the largest value of I(P,L) as for any choice of P with m elements and any choice of L with n elements. Notice that in the statement of the theorem below, m and n appear in a symmetrical way. This suggests that perhaps one can get insights into points and lines when we try interchanging their roles. Such a “duality” of points and lines holds fully in projective geometry, where any pair of lines always intersects.

Theorem (Szemerédi-Trotter, 1983):

$$I(m, n) = O\left(m^{2/3}n^{2/3} + m + n\right)$$

Informally, this theorem gives the order of magnitude that is possible for the largest number of incidences that can occur for a collection of points P with $m$ points and a collection of lines L with $n$ lines.

It is possible to show that this result is “best possible” but for the fact that the exact constant that holds for the expression above is not yet known (see below).

Before looking in more detail about the content of this result here are a few remarks about “big O” notation used in the description of the Szemerédi-Trotter theorem. The notation has a story of its own. It was originated by the German mathematician Edmund Landau (1877-1938) who is most famous as a number theorist.

In recent times big O notation is often discussed in the context of trying to determine how long it will take to run (how many steps are required) a computer algorithm in terms of some parameter of the size of the problem, typically denoted with the letter $n$. However, Landau was interested in the more general issue of comparing the growth of different functions expressed using the variable, say $n$. While sometimes in the popular press it is stated that some phenomenon is showing exponential growth, to some extent what is meant is that the phenomenon in the short run is growing faster than other functions that people may have studied in a mathematics class, like $n^2$.

The “formal” definition of “$g(x)$ is $O(f(x))$” is that $g$ obeys this property: if $x$ is larger than some fixed integer N, there is a constant C such that:

$$g(x) \leq C(f(x)) \textrm{ for } x \geq N $$

This definition says nothing about how large C or N might be. For some results of this type C and N can be huge and, thus, the result is sometimes not of “practical” computational interest.

The use of big O notation created interest in other ways to notate growth of functions or number of steps in running an algorithm. While notation may not seem an important part of the practice of mathematics, it is part of the craft by which new mathematical ideas are born and new theorems are developed. So you might want to look at the meaning of small o and big omega as notations for grown of functions.

Now that we know the meaning of big O notation we can see that the Szemerédi-Trotter Theorem says that for large enough values of $m$ and $n$, the maximum number of incidences is less than some constant times:

$$m^{2/3}n^{2/3} + m + n.$$

There is another way that the Szemerédi-Trotter Theorem can be stated that gives equivalent information but has a seemingly different flavor. Suppose we are given $m$ points in the plane and a positive integer $i \geq 2$, then the number of lines which contain at least $i$ of these points is given by:

$$O(m^2/i^3 + m/i).$$

In retrospect, it is common that the first proofs of important results are not always as insightful and as “clear” as later proofs. The original approach that Szemerédi and Trotter used to prove their result is not usually discussed because proofs that came after theirs were noticeably simpler. There are two simpler approaches to the proof that are now widely reported as approaches to this theorem. One approach exploited the use of configurations that involved a grid of points, an approach associated with the work of György Elekes(1949-2008), who died sadly at a relatively young age, as well as work due to Laszlo Szekely, which is hinted at below that involves the notion of crossing number.

One tool that has increasingly emerged as useful in discrete geometry in putting to work geometrical insights is graph theory. As we saw, graph theory concerns diagrams such as that in Figure 11.

Both of the graphs shown in Figure 13 can be regarded as a collection of points in the Euclidean plane. Note that we could have joined some of the vertices with curves to avoid the crossings that occur in the diagram but we can also interpret this diagram as a “geometric graph” where we have lines which include the points where the lines cross at what are not vertices of the original graph. One approach to connecting graph theory to questions about point and line incidences is forming a graph from the diagram representing a point set P and a line set L by constructing a graph which consists of the vertices that correspond to the points in P and joining two vertices $u$ and $v$ of this graph by edge if there is a line segment in the point/line diagram between $u$ and $v$. This leads to a graph that may be isomorphic to a plane graph, one that can be drawn in the plane without any edges meeting or crossing at points other than vertices, or may be a non-planar graph, but will typically have edges meeting at points which are called crossings–points that are not vertices of the graph involved.

Given a graph, there are many properties about the graph which one can inquire about. Thus, one can ask if a graph is planar, has a simple circuit tour that visits each vertex once and only once in a simple circuit (useful in designing a package delivery routes), has a tour of its edges that visits each edge once and only once (useful in designing snowplowing routes), etc. A natural question to ask is for the different ways to draw a graph in the plane with straight line edges (e.g. the different drawings are isomorphic), what are the smallest number and largest number of crossings of edges that can occur?

Given a graph G, cr(G) is often defined as the minimum number of crossings of edges not at vertices in any drawing of the graph G. Both graphs in Figure 13 can be redrawn with 1 crossing and, thus, have crossing number 1. The first graph shown has 5 crossings in the drawing shown and if edges are not allowed to intersect themselves or cross other edges more than once, this drawing has 5 crossings, which is the largest number of crossings. Depending on what “concepts” one is trying to understand one often puts rules on the allowed drawings. The bottom graph (Figure 13) shows three edges that pass through a single point; for some purposes such a drawing would not be allowed and one is required to use drawings where at most two edges meet at a crossing.

Given a particular graph G, to decide for any integer $c$ if the crossing number $\textrm{cr}(G) \leq c$ is known to be NP-complete. This means that it is very unlikely that there is a polynomial time algorithm for determining the solution to this question. (There are hundreds of NP-complete problems and if any one of them could be solved in polynomial time, then it would be possible to solve them all in polynomial time–no one knows!)

Over many years there has been a progression of results concerning getting bounds on the crossing number of a graph. Using the result known as Euler’s Formula that for any planar connected (one piece) graph, V + F – E = 2 where V, F and E denote the number of vertices, faces and edges of the graph. It is not difficult to see that from this result the crossing number of a general graph with V vertices (where V is at least 3) and E edges satisfies $$\textrm{cr}(G) \geq E – 3V + 6.$$

However, making various assumptions about the density of the number of edges (how rich in edges the graph is) of a graph one can get more “interesting” bounds on the crossing number.

Theorem:

$$ \textrm{If } E \geq 4V \textrm{ then cr}(G) \geq (1/64)\left(E^3/V^2\right) $$

Various variants of this result are being explored where the “edge density” is changed, in attempts to understand the value of the constant (above 1/64) in the crossing-number expression. Thinking of a configuration of points and lines in the plane as a graph drawn in the plane with crossings allows one to get the expression for incidences in the Szemerédi-Trotter Theorem.

What else can we say about the crossing number of interesting graphs? One particularly interesting family of graphs is the graphs with $n$ vertices, every pair of vertices being joined by exactly one edge–graphs known as complete graphs. Traditionally this graph is denoted $K_n$.

$K_n$ has $(n)(n-1)/2$ edges since each vertex is joined to the all of the other $n-1$ vertices, and each edge will get counted twice, once at each of its endpoints, which gives the result $(n)(n-1)/2$.

Thus, $\textrm{cr}(K_n) \geq (n)(n-1)/2 – 3n + 6,$ which simplifies to $(n^2/2) – (7/2)n + 6$.

It might seem that it would be easy to find the exact value of the crossing number of $K_n$ which is very symmetrical combinatorially, but perhaps rather surprisingly the exact value of this crossing number for every $n$ is not yet known. It has been conjectured to be Z(n):

$$(1/64)(n)(n-2)^2(n-4), \textrm{ when n is even, and}$$

$$(1/64)(n-1)^2(n-3)^2, \textrm{ when n is odd.}$$

You can check that this formula gives the crossing number of the complete graph with 5 vertices to be 1. Various people (Paul Turán and the recently deceased Richard Guy) have been involved with the “proper” guess for the minimum number of crossings of the different types of “complete” graphs drawn in the plane but the “formulas” above are sometimes associated with the name of the Polish mathematician Kazimierz Zarankiewicz. As is the spirit of mathematics, generalizing interesting ideas and concepts, there are now many kinds of crossing numbers that have been explored.

The Szemerédi-Trotter Theorem initially was concerned with incidences between points and lines. Over a period of time it resulted in new theorems related to incidences between points and pseudolines (lines are to uncooked spaghetti as pseudolines are to cooked spaghetti), points and circles of the same radius, points and circles with different radii, points on parallel lines, etc. In this line of work the result was generalized from points and lines to points and other collections of geometric sets. But if one can discuss points and lines in 2-dimensional space, why not look at points and lines in higher-dimensional spaces, or lines and planes in higher-dimensional spaces? You should not be surprised that all of these have come to be looked at and much more.

While these are seemingly natural extensions of the ideas related to the Szemerédi-Trotter Theorem there is again the element of surprise in mathematics. The Szemerédi-Trotter Theorem seems rooted in combinatorial geometry–counting things–but it also has metrical, distance-related ties. While Paul Erdős played a part in the history of the Szemerédi-Trotter Theorem (not directly discussed above) he also had a part in the this other thread of results. Given a set of points P in the plane, with different conditions on where the points are arranged with respect to each other and perhaps their pattern on lines that pass through the points, one can measure the Euclidean distance (or other distances) between points in the set P. Now one is interested in studying how few or how many distances can occur. There are many papers about counting distinct distances, repeated distances, etc.!

From little acorns great oaks grow. Incidences may seem like an “acorn” compared with other issues in mathematics but it has been an acorn that has grown impressive results. I hope you enjoy Mathematics and Statistics Awareness Month and try your hand at learning and doing some new mathematics.

References

Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society’s MathSciNet can be used to get additional bibliographic information and reviews of some of these materials. Some of the items above can be found via the ACM Digital Library, which also provides bibliographic services.

Beck, J., On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry, Combinatorica 3 (1983), 281–197.

Brass, P. and W. Moser, J. Pach, Research Problems in Discrete Geometry, Springer, New York, 2005.

Clarkson K. and H. Edelsbrunner, L. Guibas, M. Sharir, E. Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete Comput. Geom. 5 (1990) 99–160.

Dvir, Z., On the size of Kakeya sets in finite fields. J. Amer. Math Soc. 22 (2009) 1093–1097.

Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer- Verlag, Heidelberg (1987)

Elekes, G., On linear combinatorics I, Concurrency—an algebraic approach, Combinatorica 17 (4) (1997), 447–458.

Elekes, G., A combinatorial problem on polynomials, Discrete Comput. Geom. 19 (3) (1998), 383–389.

Elekes, G., Sums versus products in number theory, algebra and Erdős geometry–A survey. in Paul Erdős and his Mathematics II, Bolyai Math. Soc., Stud. 11, Budapest, 241–290 (2002)

Elekes, G., and H. Kaplan, M. Sharir, On lines, joints, and incidences in three dimensions. J. Combinat. Theory, Ser. A. 118 (2011) 962–277

P. Erdős, Problems and results in combinatorial geometry, in Discrete Geometry and Convexity (New York, 1982), vol. 440 of Ann. New York Acad. Sci., 1985, pp. 1–11.

Felsner, S., Geometric Graphs and Arrangements, Vieweg, Wiesbaden, 2004.

Grünbaum, B., Configurations of Points and LInes, Graduate Studies in Mathematics Volume 103, American Mathematical Society, Providence, 2009.

Guth, L. and N. Katz, Algebraic methods in discrete analogs of the Kakeya problem. Advances Math. 225, 2828–2839 (2010)

Guth, L. and N. Katz, On the Erdős distinct distances problem in the plane. Annals Math. 181, 155–190 (2015), and in arXiv:1011.4105.

Kaplan, H., and M. Sharir, E. Shustin, On lines and joints, Discrete Comput. Geom. 44 (2010) 838–843.

Kollar, J., Szemerédi-Trotter-type theorems in dimension 3, Adv. Math. 271 (2015), 30–61.

Matousek, J., Lectures in Discrete Geometry, Springer, New York, 2002.

Pach, J. (ed), Towards a Theory of Geometric Graphs, Contemporary Mathematics 342, American Mathematical Society, Providence, 2004.

Pach, J., and P. Agarwal, Combinatorial Geometry, Wiley, New York, 1995.

Pach, J., and R. Radoicic, G. Tardos, and G. Toth, Improving the Crossing Lemma by ?nding more crossings in sparse graphs, Discrete Comput. Geom. 36 (2006) 527–552.

Pach, J. and M. Sharir, Repeated angles in the plane and related problems, J. Comb. Theory, Ser. A 59 (1992) 12–22.

Pach, J. and M. Sharir, On the number of incidences between points and curves, Combinatorics, Probability and Computing (1998), 121–127.

Pach, J. and M. Sharir, Geometric incidences, pp. 185–224, in Towards a theory of geometric graphs, vol. 342 of Contemporary Mathematics, AMS, Providence, RI, 2004.

Pach, J. and G. Toth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997) 427–439.

Quilodran, R., The joints problem in Rn . Siam J. Discrete Math. 23 (2010) 2211–2213

Sharir, M. and E. Welzl, Point-line incidences in space. Combinat.
Prob., Comput., 13 (2004) 203–220

Sheffer, A., Distinct Distances: Open Problems and Current Bounds
https://arxiv.org/abs/1406.1949

Solymosi, J., On the number of sums and products, Bulletin of the London Mathematical Society, 37 (2005) 491–494

Solymosi, J. and Tao, T.: An incidence theorem in higher dimensions. Discrete Comput. Geom. 48 (2012) 255–280

Szekely, L., Crossing numbers and hard Erdős problems in discrete geometry, Combinatorics, Probability and Computing 6 (1997) 353–358.

Szemerédi, E., and W. T. Trotter, Extremal problems in discrete geometry, Combinatorica 3 (1983) 381-392.

Tomassia, R. (ed.), Handbook of Graph Drawing and Visualization, CRC Press, Boca Raton, 2014.

Tomassia, R. and I. Tollis (eds.), Graph Drawing, Lecture Notes in Computer Science 894, Springer, New York, 1995.

Toth, C., The Szemerédi–Trotter theorem in the complex plane, Combinatorica, 35 (2015) 95–126

Zahl, J.. and A Szemerédi–Trotter type theorem in R4, Discrete Comput.
Geom. 54, 513–572 (2015)