Calculating C(n,4) Intersection Points of Chords in a Circle with TikZ

This article explores a problem in combinatorial geometry regarding intersection points of chords inside a circle and demonstrates how to implement its algorithm using TikZ in LaTeX.

Introduction

In combinatorial geometry, there is a classic theorem regarding the relationship between points placed on a convex curve and the intersecting chords connecting them.

If we place $n$ points along the boundary of a circle (or any convex closed curve) and connect every pair of points with straight lines, we construct the complete graph $K_n$. The question arises: How many intersection points are generated inside the circle by these line segments?

Mathematically, the answer is precisely $\binom{n}{4} = C(n,4)$ intersection points (assuming no three chords intersect at a single point).

This article analyzes a TikZ implementation by Hugues Vermeiren that utilizes a 4-combination generation algorithm to automatically locate and draw all internal intersection points.

Mathematical Foundation: Why $C(n,4)$?

To understand why the number of intersection points is $C(n,4)$, consider the following geometric logic:

1. Any four distinct points ($A, B, C, D$) on the circle form a convex quadrilateral.
2. A convex quadrilateral has two diagonals, namely segments $AC$ and $BD$.
3. These two diagonals always intersect at exactly one point inside the circle.
4. Conversely, every single intersection point inside the circle is uniquely produced by the crossing of two diagonals from a unique set of 4 points.

Therefore, the total number of intersection points inside the circle equals the number of ways to choose 4 points out of $n$, given by:

For instance, with $n = 8$ points on a circle, the number of generated intersection points is:

LaTeX Source Code

Here is the complete code by Hugues Vermeiren to draw the complete graph $K_8$ and mark all 70 intersection points automatically:

% C(n,4) points of intersection
% Author: Hugues Vermeiren
\documentclass{article}
\usepackage{tikz}
\usepackage[active,tightpage]{preview}
\setlength\PreviewBorder{5pt}%
\usepackage{ifthen}
\usepackage{amsmath}
\usetikzlibrary{arrows,calc,intersections}

\begin{document}
\def\r{4}
\def\n{8}
\def\myangles{{25,50,85,125,160,220,250,280,340}} % Position angles of points

% Variables and counters used to generate the 4-combinations
\newcounter{np}
\pgfmathsetcounter{np}{\n+1}
\newcounter{na}
\newcounter{nb}
\newcounter{nc}
\newcounter{ia}
\pgfmathsetcounter{na}{\n-1}
\pgfmathsetcounter{nb}{\n-2}
\pgfmathsetcounter{nc}{\n-3}

\newcounter{q}
\setcounter{q}{0} % exit flag
\newcounter{e}
\setcounter{e}{0} % combination / intersection counter
\newcounter{a}
\setcounter{a}{0}
\newcounter{b}
\setcounter{b}{1}
\newcounter{c}
\setcounter{c}{2}
\newcounter{d}
\setcounter{d}{2}

\begin{preview}
Consider $n$ randomly placed points on a circle.
\begin{enumerate}
  \item The complete graph on the $n$ points has $\begin{pmatrix}n\\2\end{pmatrix}$ edges.
  \item Each pair of edges yields an intersection point and there are (at most) $\begin{pmatrix}n\\4\end{pmatrix}$ such points.
\end{enumerate}

\begin{center}
\begin{tikzpicture}
% 1. Draw the Complete Graph K_n
\fill[fill=blue!10!green!10!,draw=blue,dotted,thick] (0,0) circle (\r);
\pgfmathparse{\n-1}
\let\nn\pgfmathresult

\foreach \i in {0,...,\nn}{
  \pgfmathparse{\i+1}
  \let\ii\pgfmathresult
  \pgfmathparse{\myangles[\i]}
  \let\t\pgfmathresult
  \foreach \j in {\ii,...,\n} {
    \pgfmathparse{\myangles[\j]}
    \let\u\pgfmathresult
    \draw[blue,very thick] ({\r*cos(\t)},{\r*sin(\t)})--({\r*cos(\u)},{\r*sin(\u)});
  }
}

% 2. Draw Node Points on the Circle
\foreach \i in {0,...,\n}{
  \pgfmathparse{\myangles[\i]}
  \let\t\pgfmathresult
  \pgfmathsetcounter{ia}{\i+1}
  \fill[draw=blue,fill=blue!20!,thick] ({\r*cos(\t)},{\r*sin(\t)}) circle (2.5mm) node{$\mathbf{\theia}$};
}

% 3. Loop Algorithm for C(n,4) Combinations & Intersection Plotting
\whiledo{\theq=0}{
  \stepcounter{e}
  \ifthenelse{\thee=1000}{\setcounter{q}{1}}{}% safety exit
  \ifthenelse{\thed=\n}
    {\ifthenelse{\thec=\thena}
      {\ifthenelse{\theb=\thenb}
        {\ifthenelse{\thea=\thenc}
          {\setcounter{q}{1}}
          {
            \stepcounter{a}
            \pgfmathsetcounter{b}{\thea+1}
            \pgfmathsetcounter{c}{\thea+2}
            \pgfmathsetcounter{d}{\thea+3}
          }
        }
        {
          \stepcounter{b}
          \pgfmathsetcounter{c}{\theb+1}
          \pgfmathsetcounter{d}{\theb+2}
        }
      }
      {
        \stepcounter{c}
        \pgfmathsetcounter{d}{\thec+1}
      }
    }
    {\stepcounter{d}}
    
  \ifthenelse{\theq=0}{
    % Compute Coordinates for 4 Points
    \pgfmathparse{\r*cos(\myangles[\thea])} \let\xa\pgfmathresult
    \pgfmathparse{\r*sin(\myangles[\thea])} \let\ya\pgfmathresult
    \pgfmathparse{\r*cos(\myangles[\theb])} \let\xb\pgfmathresult
    \pgfmathparse{\r*sin(\myangles[\theb])} \let\yb\pgfmathresult
    \pgfmathparse{\r*cos(\myangles[\thec])} \let\xc\pgfmathresult
    \pgfmathparse{\r*sin(\myangles[\thec])} \let\yc\pgfmathresult
    \pgfmathparse{\r*cos(\myangles[\thed])} \let\xd\pgfmathresult
    \pgfmathparse{\r*sin(\myangles[\thed])} \let\yd\pgfmathresult
    
    \coordinate (A) at (\xa,\ya);
    \coordinate (B) at (\xb,\yb);
    \coordinate (C) at (\xc,\yc);
    \coordinate (D) at (\xd,\yd);
    
    % Define Diagonal Paths
    \path[name path=sega] (A) -- (C);
    \path[name path=segb] (B) -- (D);
    
    % Compute Intersections via TikZ Intersections Library
    \path [name intersections={of=sega and segb}];
    \coordinate (X) at (intersection-1);
    \fill[fill=green!50!,draw=blue] (X) circle (0.8mm);
  }{}
}
\end{tikzpicture}
\end{center}

\addtocounter{e}{-1}
Number of generated intersection points : \thee
\end{preview}
\end{document}

Compiled Output

The resulting graphical output displays a beautiful symmetrical web of lines punctuated by green dots at each intersection:

Detailed Code Analysis

1. Key Libraries & Package Setup

• intersections: An essential TikZ library (\usetikzlibrary{intersections}) that automatically computes line-line intersections without requiring manual slope or intercept calculations.
• ifthen: Provides control structures like \ifthenelse and \whiledo in standard LaTeX environments.

2. Building the Complete Graph $K_n$

• The array \myangles stores the polar position of each of the 8 points.
• Nested loops \foreach \i and \foreach \j connect every pair $i$ and $j$ ($0 \le i < j \le n$) with blue lines \draw[blue,very thick]. The total number of drawn chords is: $\binom{8}{2} = \frac{8 \times 7}{2} = 28 \text{ edges}$

3. The 4-Combination Generator

• The loop \whiledo{\theq=0} implements a lexicographical combination algorithm to produce tuples $(a, b, c, d)$ such that $a < b < c < d$.
• This guarantees that every set of 4 points is evaluated exactly once.

4. Interactive Intersection Finding

• For each 4-point set $(A, B, C, D)$, two diagonal paths sega ($A \to C$) and segb ($B \to D$) are generated without drawing.
• Command \path [name intersections={of=sega and segb}]; computes the meeting point and names it (intersection-1).
• A green dot is plotted at coordinate (X) via \fill[fill=green!50!,draw=blue] (X) circle (0.8mm);.

TikZ Experimentation

Try these modifications to explore further:

1. Varying Point Count ($n$): Change \def\n{8} to \def\n{6} for $\binom{6}{4} = 15$ points, or \def\n{10} for $\binom{10}{4} = 210$ points.
2. Regular Polygon Placement: Replace the manual \myangles vector with uniform angular steps:
   latex

   \pgfmathsetmacro{\t}{\i * 360 / \n}

3. Radial Color Mapping: Color intersection points according to their radial distance from the origin for a vibrant aesthetic effect.

Conclusion

This TikZ script beautifully bridges combinatorial mathematics and computational geometry. By leveraging TikZ’s intersections library, the exact physical positions of dozens of chord intersections are generated automatically from elementary combination rules.

References

1. Hugues Vermeiren, Points of intersection, TeXample.net
2. Till Tantau, The TikZ and PGF Manual, v3.1.10, 2024.
3. Graham, R. L., Knuth, D. E., & Patashnik, O., Concrete Mathematics: A Foundation for Computer Science.

Written by: Aan Triono
License: CC BY-SA 4.0