# The Dirac–Goodman–Pollack Conjecture

Adrian Dumitrescu Algoresearch L.L.C., Milwaukee, WI, USA. Email
<EMAIL_ADDRESS>
###### Abstract

In one of their seminal articles on allowable sequences, Goodman and Pollack
gave combinatorial generalizations for three problems in discrete geometry,
one of which being the Dirac conjecture. According to this conjecture, any set
of $n$ noncollinear points in the plane has a point incident to at least $cn$
connecting lines determined by the set. The notion of allowable sequences of
permutations provides a natural combinatorial setting for analyzing these
problems. Within this formalism, the conjectured generalization reads as
follows: _Any nontrivial allowable $n$-sequence $\Sigma$ has a local sequence
$\Lambda_{i}$ whose half-period is at least $cn$._ The conjecture is confirmed
here with a concrete bound $c=1/845$. Several related problems are discussed.

Keywords: allowable sequence, Dirac’s conjecture, Sylvester’s problem, the
crossing lemma, the Szemerédi–Trotter theorem, Székely’s method.

##  1 Introduction

In one of their seminal articles on allowable sequences [27] Goodman and
Pollack gave combinatorial generalizations (left as conjectures) for the
following three problems in discrete geometry:

  1. $\mathrm{A}$

the Erdős–Szekeres conjecture that any $2^{n-2}+1$ points in general position
in the plane contains $n$ points in convex position,

  2. $\mathrm{B}$

the Dirac conjecture that any set of $n$ noncollinear points in the plane
contains a point incident to at least $cn$ connecting lines determined by the
set, for some constant $c>0$,

  3. $\mathrm{C}$

the problem of finding the minimum number of directions determined by $n$
noncollinear points in the plane.

The notion of allowable sequences of permutations provides a natural
combinatorial setting independent from geometry for analyzing these problems
and making them more transparent. Within this formalism, the conjectured
generalizations for the three statements above read as follows:

  1. $\mathrm{A^{\prime}}$

[27] Let $\Sigma$ be an allowable $2^{n-2}+1$-sequence in which only strings
of length two are reversed. Then there are $n$ indices such that each occurs
before or after the others in some term of $\Sigma$.

  2. $\mathrm{B^{\prime}}$

[27] Any nontrivial allowable $n$-sequence $\Sigma$ has a local sequence
$\Lambda_{i}$ whose half-period is at least $cn$, for some constant $c>0$.

  3. $\mathrm{C^{\prime}}$

[27] If $\Sigma$ is a nontrivial allowable $n$-sequence, the half-period of
$\Sigma$ is at least $2\lfloor n/2\rfloor$.

The formalism as well as our results will be made precise in Section 2, at the
end of which we state our results and review the status of the three problems
and their generalizations. It will be evident at that point that
$\mathrm{A^{\prime}}\implies\mathrm{A}$,
$\mathrm{B^{\prime}}\implies\mathrm{B}$, and
$\mathrm{C^{\prime}}\implies\mathrm{C}$, though not conversely. Our goal in
this paper is the proof of Statement $\mathrm{B^{\prime}}$.

### Connecting lines and a theorem of de Bruijn and Erdős.

Before discussing Dirac’s conjecture, it is natural to mention how this
question appeared in the broader context of estimating the total number of
connecting lines determined by a noncollinear point set (clearly the answer is
$1$ for collinear sets). Theorem 2 below provides the answer.

Historically, the study of point sets and their connecting lines draws from a
question asked by Sylvester [52] about $50$ years earlier: _For a finite set
of points, not all on a line, does there always exist a line that contains
exactly two of the points?_ If the answer is positive, the corresponding
equivalent statement would read: if for every pair of points in the set, the
line determined by these points contains a third one, then all the points are
collinear. Given a point set $S$, a connecting line (i.e., a line determined
by the set) is called _ordinary_ if it contains precisely two points of $S$;
see also [7]. Sylvester problem got forgotten over time but was rediscovered
by Erdős [16] in $1943$.

The first proof of existence of an ordinary line dates back to those times and
it is now commonly referred to as the _Sylvester–Gallai Theorem_ (solutions
were found by several researchers). Its colorful history is recounted by
Chvátal in his recent monograph [10]. Earlier accounts on its development can
be found in [8, 11, 19, 34, 46].

######  Theorem 1.

(Sylvester–Gallai). Every set of $n$ noncollinear points in the plane admits
an ordinary line.

Motzkin [40] was the first to show that the number of ordinary lines tends to
infinity with $n$. Further, Kelly and Moser [33] proved that there are at
least $3n/7$ ordinary lines, and Csima and Sawyer [11] raised this bound to
$6n/13$ for $n\geq 8$. Finally, Green and Tao [29] proved that if $n$ is
sufficiently large then there are at least $n/2$ ordinary lines, thereby
settling the so called strong Dirac–Motzkin conjecture for large $n$ (even
though neither of the authors seem to have conjectured this in print, see
[29]). On the other hand, there are arbitrarily large points sets with no more
than $n/2$ ordinary lines: for even $n$, take a regular $n/2$-gon, which
determines $n/2$ directions, and the $n/2$ projective points corresponding to
these directions; see [8, Ch. 7.2].

Erdős [16] deduced the following interesting corollary of Theorem 1. Here the
term _near-pencil_ describes a point set that is almost collinear, in the
sense that all but of one the points are collinear.

######  Theorem 2.

(Erdős [16]). For a set of $n$ noncollinear points in the plane, the number of
connecting lines is always at least $n$; and it is equal to $n$ if and only if
the points form a near-pencil.

In fact every other configuration determines more lines as quantified in the
following result of Kelly and Moser [33].

######  Theorem 3.

(Kelly and Moser [33]). Let $S$ be a set of $n$ points and let
$\lambda=\lambda(S)$ denote the number of connecting lines. If at most $n-k$
points of $S$ are collinear and $n>\frac{1}{2}\\{3(3k-2)^{2}+3k-1\\}$ then
$\lambda\geq kn-\frac{1}{2}(3k+2)(k-1)$.

In particular ($k=2$), if at most $n-2$ points are collinear and $n\geq 27$,
the number of connecting lines is always at least $2n-4$; the lower bound
actually holds for $n\geq 10$, see [34, Ch. 6].

Perhaps even more interesting than Theorem 2 is the following result of de
Bruijn and Erdős [18] from about the same time—which provides the same answer
under more general circumstances that distill the essential features present
in the theorem. See also [37, Ch. 19], [44].

######  Theorem 4.

(de Bruijn and Erdős [18]). Let $(V,E)$, $|V|=n$, $|E|=m$, be a hypergraph,
where every pair of elements in $V$ is contained in precisely one edge in $E$.
Then $m\geq n$, with equality if and only if (i) one of the sets contains all
but one elements of $V$ and the others are two-element sets containing the
remaining element; or (ii) $E$ is the system of lines of a finite projective
plane defined on $V$.

A result of Motzkin [41], Rabin, and Chakerian [9] states that any set of $n$
two-colored (say, by red or blue) noncollinear points in the plane determines
a monochromatic line; see also [2, Ch. 13].

### Dirac’s conjecture.

For a noncollinear set $S$ of $n$ points in the plane, let $t(S)$ be the
minimum number of lines spanned be $S$ that are incident to a point in $S$;
let $t(n)$ be the minimum of $t(S)$ over all point sets of size $n$. In a dual
setting, for a set $\mathcal{L}$ of $n$ lines in the plane, no two of which
are parallel, let $r(\mathcal{L})$ be the maximum number of crossing points
(vertices of the line arrangement) on a line in $\mathcal{L}$.

G. A. Dirac [12] and T. S. Motzkin [40], independently of each other and at
the same time proposed the following problem: Does every noncollinear set of
points contain some point that is incident to at least $n/2$ lines determined
by the set? Initially Dirac proved that there are at least $\sqrt{n+1}$ lines
incident to one of the points and conjectured the existence of a point
incident to at least $\lfloor n/2\rfloor$ connecting lines. Several
counterexamples were found by Grünbaum (for $n=9,15,19,25,31$, and $37$), see
[30] and [11, F12], and so the conjecture has been modified [17] to read as
follows:

######  Conjecture 1.

(Dirac). Given a set $S$ of $n$ noncolllinear points in the plane, there
exists a point in $S$ incident to $cn$ lines determined by $S$, for some
constant $c>0$.

From the other direction, Akiyama et al. [4] considered the problem of finding
noncollinear point sets $S$ with $t(S)\leq\lfloor n/2\rfloor$. They showed
that for every $n\geq 8$ of the form $n=12k+r$, $r\neq 11$, there exists a set
$S$ of $n$ noncollinear points satisfying $t(S)\leq\lfloor n/2\rfloor$. An
infinite family of counterexamples to the strong Dirac conjecture was found by
Felsner [8, p. 313]. In the dual setting it consists of $6k+7$ lines in the
real projective plane (r.p.p.) where no line is incident to more than $3k+2$
points of intersection. In a stronger form—the so called _strong Dirac
conjecture_ —the bound is replaced by $n/2-c$, where $c>0$ is a constant [42];
see also [8, Ch. 7.3].

In $1983$ Beck [5] proved the following result and further observed that
Conjecture 1 immediately follows from it.

######  Theorem 5.

(Beck [5]). Let $S$ be a set of $n$ points in the plane. If at most $\ell$
points of $S$ are collinear, then $S$ determines at least $\Omega(n(n-\ell))$
distinct lines.

At about the same time Szemerédi and Trotter [54] obtained their classic
result on the number of point-lines incidences in the plane: Theorem 6 or 7
below. Their result also implies Conjecture 1. Interestingly enough, as
remarked by Székely [53], Beck obtained his result on connecting lines from a
result weaker than the Szemerédi–Trotter theorem.

Here we give two equivalent formulations of the Szemerédi and Trotter result.
Given a point set $S$ in $\mathbb{R}^{2}$, for any integer $k\geq 2$, a line
is called _$k$ -rich_ if it is incident to at least $k$ points of $S$.

######  Theorem 6.

(Szemerédi–Trotter [54]). The number of point-line incidences among $n$ points
and $\ell$ lines in $\mathbb{R}^{2}$ is

$I(n,\ell)=\mathcal{O}(n^{2/3}\ell^{2/3}+n+\ell).$

######  Theorem 7.

(Szemerédi–Trotter [54]). Given $n$ points in $\mathbb{R}^{2}$, the number of
$k$-rich lines, $k\geq 2$, is

$\mathcal{O}\left(n^{2}/k^{3}+n/k\right).$

The resulting constants, however, in the above proofs for Conjecture 1 are
quite small; for instance, the constant obtained in [54] is $10^{-1087}$; see
also [34, Ch. 6]. New developments in the theory of geometric graphs have lead
over time to better constants in Dirac’s conjecture. One such tool is the
classic crossing lemma proved in the early 1980s by Ajtai, Chvátal, Newborn,
and Szemerédi [3] and Leighton [36]. The sharper constant appearing at the end
of the lemma was established recently by Ackerman [1] who improved an earlier
bound by Pach, Radoičić, Tardos, and Tóth [45]; see also [46, Ch. 4].

######  Lemma 1.

(Ajtai, Chvátal, Newborn, and Szemerédi [3] Leighton [36], Ackerman [1]). Let
$G=(V,E)$, where $|V|=n$, $|E|=e$, be a simple graph with with $n$ vertices
and $e\geq 4n$ edges. Then ${\rm cr}(G)\geq c\cdot e^{3}/n^{2}$, for a
suitable constant $c>0$. In particular, one may take $c=1/64$; and if $e\geq
6.95n$, then one may take $c=1/29$.

Another key development is due to Székely [53], whose groundbreaking approach
of constructing suitable graphs and running the crossing lemma machinery led
to new bounds and improved constants in relation to Dirac’s conjecture, but in
many other problems as well. For instance, using this approach, Payne [47]
showed in his thesis that Conjecture 1 holds with $c=2^{-15}$; see also [48].
Further, Payne and Wood [48] raised the bound to $c=1/37$; notably,
Hirzebruch’s inequality is used in their proof; see also [8, Ch. 7]. Pham and
Phi refined the argument of Payne and Wood and improved the bound to $c=1/26$
[49]. Recently, Han [31] established the current best result in Dirac’s
conjecture, showing that there is a point incident to $\left\lceil
n/3\right\rceil+1$ connecting lines; notably, the Bojanowski–Pokora inequality
is used in their proof. His result answers a question of Klee and Wagon [34,
Ch. 6]; the same question was reposed $20$ years later by Akiyama et al. [4].

In regard to the proof techniques, it is worth mentioning that neither the
Hirzebruch’s inequality nor the Bojanowski–Pokora inequality are known to hold
in a pseudoline setting (discussed in Section 2).

### Outline of the paper.

Section 2 gives an overview of pseudoline arrangements and allowable sequences
and lists our results. The main results are the lower bounds in Theorems 8 and
9 in relation to Conjecture 2 in Section 2 (i.e., Statement
$\mathrm{B^{\prime}}$ at the beginning of Section 1). The upper bound in
Theorem 10 gives a partial answer to a question of Lund, Purdy and Smith [39].
Section 3 contains the proofs of Theorems 8 and 9. Section 4 contains the
proof of Theorem 10.

##  2 Pseudolines, allowable sequences, and wiring diagrams

### Pseudoline arrangements.

A family (collection) of two-way infinite $x$-monotone curves in the plane is
called an _(Euclidean) arrangement of pseudolines_ if any two curves have
precisely one point in common, at which they properly cross [22, Ch. 6]. An
arrangement is _simple_ if no three pseudolines have a common point of
intersection, see Fig. 1 (left). An arrangement is _nontrivial_ if not all
pseudolines cross at a single point.

Figure 1: Left: A simple arrangement $\mathcal{A}$. Center: Wiring diagram of
$\mathcal{A}$. Right: An arrangement $\mathcal{A}^{\prime}$ that is not
isomorphic to the arrangement $\mathcal{A}$ on the left.

A family $\mathcal{P}$ of pseudolines is _stretchable_ if there exists a
family of lines $\mathcal{L}$ such that the cell decompositions induced by
$\mathcal{P}$ and $\mathcal{L}$ are topologically isomorphic. Two arrangements
are _isomorphic_ , i.e., considered the same, if they can be mapped onto each
other by a homeomorphism of the plane [24]; see Fig. 1 (right). Equivalently,
two arrangements are isomorphic if there is an isomorphism between the induced
cell decompositions [22, Ch. 6]. Two classic representations of pseudoline
arrangements are _allowable sequences_ [26, 28] and _wiring diagrams_ [23].

### Allowable sequences.

Let $P$ be a set of $n$ points in the plane and assume that no two points have
the same $x$-coordinate. Label the points of $P$ by $1,2,\ldots,n$ in
increasing order of their $x$-coordinate. Take a horizontal line $\ell$ and
start rotating it counterclockwise about a fixed point; In each position, the
order of the orthogonal projections of the elements of $P$ onto $\ell$ makes a
permutation of $1,2,\ldots,n$. As the line $\ell$ rotates counterclockwise
about a fixed point, we obtain a periodic sequence of permutations which is
called the _circular sequence_ of the configuration [27]; see also [14, Ch.
2], [22, Ch. 6], [23], [46, Ch. 1]. The first half-period of this sequence
starts with the identity permutation $1,2,\ldots,n$ and ends with its
reversal, $n,n-1,\ldots,1$; this corresponds to a rotation of $\ell$ by
$180^{\circ}$. During this half-period the following rule is in effect:

  1. 1.

Every permutation is obtained from the previous one by reversing one or more
nonoverlapping increasing subsequences of adjacent elements.

If the rotation of $\ell$ continues, we obtain the same sequence of
permutations as before, except that now each of them is reversed. After a
complete rotation of $360^{\circ}$, we get back $1,2,\ldots,n$, the
permutation we started with. And so one is usually interested only in the
sequence for the first half-period.

Goodman and Pollack [27] generalized this process associated with a point set
to an abstract setting. Any sequence of permutations that starts with
$1,2,\ldots,n$, ends in $n,n-1,\ldots,1$, and satisfies the above rule is
called an _allowable sequence_ (or _$n$ -sequence_). The _half-period_ of this
sequence is one less than the number of permutations in the sequence i.e., the
number of _steps_ (or _moves_) in the process111If convenient, the process can
be extended beyond the term $n,n-1,\ldots,1$, so that a periodic sequence of
permutations results that cycles back to $1,2,\ldots,n$. Terms a half-period
apart are the reverses of each other. However, this extension won’t be needed
here.. An allowable sequence $\Sigma$ is _simple_ if any two consecutive
permutations in $\Sigma$ differ by the reversal of an adjacent pair $ij$,
where $i<j$. An allowable sequence is _nontrivial_ if it has more than two
permutations; equivalently $1,2,\ldots,n$ is not reversed in one step.
Throughout this paper, we only consider nontrivial sequences.

One can extract an allowable sequence of permutations from any given
arrangement of pseudolines by sweeping a vertical line from left to right and
recording the switches that occur in that order. Even though not every
allowable sequence is geometrically realizable as the circular sequence
generated by a set of points (or lines), it is however true that every
allowable sequence is realizable as the $n$-sequence generated by an
arrangement of pseudolines [28]. Write each permutation in the sequence as a
vertical column of $n$ numbers and put the columns one after the other. The
$i$th pseudoline is the piecewise linear $x$-monotone curve obtained by
connecting all occurrences of number $i$, for $i=1,2,\ldots,n$ and extended
both ways to infinity. By construction, this family of curves is a pseudoline
arrangement whose sweep-sequence is the given allowable sequence. By this
equivalence, in our arguments we may use language that applies to one setting
(allowable sequences) or the other one (pseudolines) as convenient.

Let $\Sigma$ be an allowable $n$-sequence. For each $i\in[n]$, its _local
sequence_ $\Lambda_{i}(\Sigma)$ is the sequence of reversals involving the
index $i$. Obviously such reversals appear in succession, i.e., no two are
simultaneous. The _half-period_ (or _length_) of a local sequence is the
number of reversals in the sequence.

Figure 2: Wiring diagrams of a simple arrangement (left) and a non-simple one
(right).

### Wiring diagrams.

A  _wiring diagram_ is an Euclidean arrangement of pseudolines consisting of
piece-wise linear ‘wires’, each horizontal except for shorter slanted segments
where it crosses other wires. Each pair of wires cross exactly once; see Fig.
1 (center). Wiring diagrams are also known as _reflection networks_ , i.e.,
networks that bring $n$ wires labeled from $1$ to $n$ into their reflection by
means of performing switches of (two or more) adjacent wires [35, p. 35]. For
example, the $5$-sequence for the wiring diagram in Fig. 2 (right) is

$12345\xrightarrow{12,45}21354\xrightarrow{135}25314\xrightarrow{25,14}52341\xrightarrow{34}52431\xrightarrow{24}54231\xrightarrow{23}54321.$

Its half-period is $6$. Its five local sequences are the following.
$\Lambda_{1}=12,135,14$; $\Lambda_{2}=12,25,24,23$; $\Lambda_{3}=135,34,23$;
$\Lambda_{4}=45,14,34,24$; and $\Lambda_{5}=45,135,25$. The half-period of
$\Lambda_{5}$ is $3$.

### Applications of allowable sequences.

A classic example is the result of Ungar mentioned in the introduction on the
minimum number of directions determined by $n$ noncollinear points in the
plane. If $D(n)$ denotes this number, Ungar [55] showed that $D(n)=2\lfloor
n/2\rfloor$, which is tight for the near-pencil configuration. His proof via
allowable sequences concentrates on the subsequence of switches crossing the
midline that separates the first $n/2$ elements from the last $n/2$ elements
(assuming that $n$ is even). Another key result is one obtained by
Edelsbrunner and Welzl [15] in the study of $k$-sets; they showed that the
number of $k$-sets in a set of $n$ points is $\mathcal{O}(nk^{1/2})$; see also
[14, Ch. 2]. More recent applications can be found in [13] and [43]. In the
latter article, Nilakantan obtained an alternative proof of Theorem 1 via
allowable sequences by arguing the existence of a _simple switch_ , namely one
that involves only two elements.

### Dirac–Goodman–Pollack conjecture for pseudolines.

For an arrangement $\mathcal{L}$ of pseudolines let $r(\mathcal{L})$ be the
maximum number of crossing points (vertices of the line arrangement) on a
pseudoline in $\mathcal{L}$. The conjecture can be formulated in terms of
allowable sequences (as mentioned in Section 1) or in terms of systems of
pseudolines. The latter formulation is as follows.

######  Conjecture 2.

[12, 27] Let $\mathcal{L}$ be a nontrivial arrangement of $n$ pseudolines.
Then $r(\mathcal{L})\geq cn$, for some constant $c>0$.

Lund, Purdy and Smith [39] claimed that such a bound holds, but did not
provide any proof. From the other direction, they constructed arrangements
with $r(\mathcal{L})\leq\frac{4}{9}n$. Regardless, here we obtain the first
concrete lower bound (Theorem 8) and an extension for many pseudolines
(Theorem 9).

######  Theorem 8.

Let $\mathcal{L}$ be a nontrivial arrangement of $n$ pseudolines. Then there
is a pseudoline in $\mathcal{L}$ that is incident to at least $cn$ crossing
points. In particular, one may take $c=1/845$ for large $n$.

######  Theorem 9.

Let $0<\delta<1$ be any constant. Consider an arrangement of pseudolines in
which every crossing involves at most $\delta n$ elements. Then there exist
$\Omega(n)$ pseudolines whose local sequences have length (i.e., half-period)
$\Omega(n)$.

From the other direction, an old construction studied by Rigby [50] shows the
following.

######  Theorem 10.

There is an infinite family of arrangements of $n$ lines (as a system of
pseudolines), such that

  * •

each vertex is incident to at most $3$ lines, and

  * •

no line is incident to more than $\frac{1}{2}\,n+\mathcal{O}(1)$ vertices.

We end this section with a brief review of the status of the three problems
and their generalizations (from Section 1). Statement $\mathrm{C^{\prime}}$
has been settled by Ungar in 1982 [55]. Statement $\mathrm{B^{\prime}}$ is
proved in Theorem 8 with a bound of $n/845$ (for $n$ sufficiently large).
Statement $\mathrm{A^{\prime}}$ remains open, however, recent results are
closing in on this problem. Let $f(n)$ denote the minimum number of points in
general position that determine a convex $n$-gon. For the geometric variant
$\mathrm{A}$, Erdős and Szekeres [20, 21] proved many years ago that
$2^{n-2}+1\leq f(n)\leq 4^{n(1-o(1))}$; after several constant-factor
improvements by other researchers that we skip here, Suk [51] managed to bring
the upper bound to same base as the lower bound, i.e., $f(n)\leq
2^{n+\mathcal{O}(n^{2/3}\log{n})}$. Holmsen, Mojarrad, Pach, and Tardos [32]
generalized Suk’s result to pseudoline arrangements and improved the error
term. The improvement carries over to the geometric variant and implies
$f(n)\leq 2^{n+\mathcal{O}(\sqrt{n\log{n}})}$.

##  3 Proofs of the main results

In this section we prove Theorems 8 and 9. The key component in the proof is a
dual extension of the Szemerédi–Trotter theorem for point-line incidences to
arrangements of $x$-monotone pseudolines. We employ Székely’s method [53]. Let
$2\leq k\leq n$. A crossing point is $k$-_rich_ if it is incident to at least
$k$ pseudolines.

######  Lemma 2.

Let $5\leq k\leq n-1$. For an arrangement of $n$ pseudolines, the number of
$k$-rich crossing points is at most

$c_{1}\frac{n}{k}+c_{2}\frac{n^{2}}{k^{3}},$ (1)

for a suitable constants $c_{1},c_{2}>0$. In particular, one may take
$c_{1}=5$ and $c_{2}=125/2$; and if $k\geq 8$ one may take $c_{1}=14$ and
$c_{2}=18.12$.

###### Proof.

Construct a graph $G=(V,E)$ drawn in the plane, where $V$ is the set of
$k$-rich crossing points in $\mathcal{A}$ and edges connect vertices along the
pseudolines in $\mathcal{A}$. Let $|V|=m$. Refer to Fig. 3 for an example.

Figure 3: The graph $G$; here $n=9$, $k=3$, $m=9$, and $|E|=19$.

The graph $G$ is simple since every pair of pseudolines cross exactly once.
Since $\mathcal{A}$ is an arrangement of $n$ pseudolines, ${\rm
cr}(G)\leq{n\choose 2}$. We have $|V|=m$ and $|E|\geq km-n$ by easy counting.
We distinguish two cases.

_Case 1._ $km\leq 5n$. Then $m\leq 5n/k$, as required.

_Case 2._ $km\geq 5n$. Then $|E|\geq km-km/5=4km/5\geq 4m$ by the assumption
$k\geq 5$. The former setting of the crossing lemma (Lemma 1) can be applied
and it gives

${n\choose 2}\geq{\rm cr}(G)\geq\frac{|E|^{3}}{64|V|^{2}},\text{ or
}n^{2}\geq\frac{2}{64}\cdot\frac{4^{3}}{5^{3}}\cdot\frac{k^{3}m^{3}}{m^{2}}.$

It follows that $m\leq\frac{125}{2}\,\frac{n^{2}}{k^{3}}$, as required.

Assume now that $k\geq 8$. We distinguish two cases.

_Case 1._ $km\leq 14n$. Then $m\leq 14n/k$, as required.

_Case 2._ $km\geq 14n$. Then $|E|\geq km-km/14=13km/14\geq 7m$ by the
assumption $k\geq 8$. The latter setting of the crossing lemma can be applied
and it gives

${n\choose 2}\geq{\rm cr}(G)\geq\frac{1}{29}\frac{|E|^{3}}{V|^{2}},\text{ or
}n^{2}\geq\frac{2}{29}\cdot\frac{13^{3}}{14^{3}}\cdot\frac{k^{3}m^{3}}{m^{2}}.$

It follows that $m\leq 18.12\,\frac{n^{2}}{k^{3}}$, as required. ∎

Showing that $\Sigma$ has a local sequence $\Lambda_{i}$ whose half-period is
$\Omega(n)$ is equivalent to showing that at least one pseudoline is incident
to $\Omega(n)$ crossing points (these may be vertices of $G$ or edge crossings
with the respective pseudoline).

######  Observation 1.

Let $\mathcal{L}^{\prime}\subset\mathcal{L}$ be the subset of pseudolines
participating in a crossing $\xi$ and
$\ell\in\mathcal{L}\setminus\mathcal{L}^{\prime}$ be any other pseudoline.
Then $\ell$ must cross every pseudoline in $\mathcal{L}^{\prime}$ at a
different crossing point.

###### Proof.

Let $\mathcal{L}^{\prime\prime}\subset\mathcal{L}$ be the subset of
pseudolines participating in a fixed crossing other than $\xi$. Then
$|\mathcal{L}^{\prime}\bigcap\mathcal{L}^{\prime\prime}|\leq 1$, since every
pair of pseudolines cross exactly once. Since $\ell$ must cross every other
pseudoline, in particular, every pseudoline in $\mathcal{L}^{\prime}$, $\ell$
must have at least $|\mathcal{L}^{\prime}|$ different crossing points. ∎

Note that the condition on the uniqueness of any pairwise intersection (as
above) is essentially the same as that appearing in Theorem 4; see also [37,
Ch. 19].

### Proof of Theorem 8.

First assume that there exists a $k$-rich crossing point $\xi$ for $k=n/845$.
Consider the subset of pseudolines $\mathcal{L}^{\prime}\subset\mathcal{L}$
involved in this crossing. We have $|\mathcal{L}^{\prime}|\geq n/845$; recall
that $|\mathcal{L}^{\prime}|\leq n-1$. Pick any pseudoline
$\ell\in\mathcal{L}\setminus\mathcal{L}^{\prime}$. By Observation 1, $\ell$
must intersect every element in $\mathcal{L}^{\prime}$ at a different crossing
point. In other words, the length of $\ell$’s local sequence is at least
$|\mathcal{L}^{\prime}|\geq n/845$, as required.

We may now assume for the remainder of the proof that there are no $k$-rich
crossing points for $k=n/845$. Since every pair of pseudolines intersect
exactly once, the total number of pair switches is ${n\choose 2}$. We next
compute an upper bound on the number of pair switches at the $k$-rich crossing
points for $256\leq k<n/845$. Since $k\geq 8$, we can use the latter setting
of Lemma 2, with $c_{1}=14$ and $c_{2}=18.12$. Once this bound is obtained, we
deduce from it (and the total count) a lower bound on the total number of
switches at $k$-rich crossing points for $2\leq k\leq 255$. Finally we obtain
a lower bound on the maximum number of crossings on some pseudoline in
$\mathcal{L}$.

For $i\geq 1$, let $V_{i}\subset V$ denote the subset of vertices incident to
at least $2^{i}$ and at most $2^{i+1}-1$ pseudolines. Observe that a vertex in
$V_{i}$ contributes fewer than ${2^{i+1}\choose 2}\leq 2\cdot 4^{i}$ switches
(out of ${n\choose 2}$).

Let $N_{1}$ denote the number of switches at $k$-rich vertices for $256\leq
k<n/845$ contributed by the first term (linear in $n$) in Equation (1). Let
$x$ be the minimum integer such that $2^{x+1}\geq n/845$. Then $2^{x}<n/845$,
whence we have

$\displaystyle N_{1}$ $\displaystyle\leq
c_{1}n\sum_{i=8}^{x}\frac{1}{2^{i}}{2^{i+1}\choose 2}\leq
2c_{1}n\sum_{i=8}^{x}2^{i}\leq 4c_{1}n\,2^{x}\leq
4c_{1}n\left(\frac{n}{845}\right)\leq\frac{4.242}{64}n^{2}.$

Let $N_{2}$ denote the number of switches at $k$-rich vertices for $256\leq
k<n/845$ contributed by the second term (quadratic in $n$) in Equation (1). We
have

$\displaystyle
N_{2}\leq\sum_{i=8}^{\infty}c_{2}\frac{n^{2}}{2^{3i}}{2^{i+1}\choose 2}\leq
2c_{2}n^{2}\left(\sum_{i=8}^{\infty}\frac{1}{2^{i}}\right)=2c_{2}\frac{1}{128}n^{2}=\frac{18.12}{64}n^{2}.$

Adding up the two contributions yields

$N_{1}+N_{2}\leq\frac{22.362}{64}n^{2}.$

Hence at least

${n\choose 2}-\frac{22.362}{64}n^{2}\geq\frac{9.637}{64}n^{2}$ (2)

switches occur at crossing points that involve at most $255$ pseudolines. In
the last inequality we used the fact that $n$ is large enough. A crossing of
$j$ pseudolines, where $2\leq j\leq 255$, distributes $j$ credits to the
respective lines and uses ${j\choose 2}$ switches from the pool in (2). One
credit received by a pseudoline counts for one crossing point on the
respective pseudoline. The ratio of credits to switches in such a crossing,

$\frac{j}{{j\choose 2}}=\frac{2}{j-1},$

is minimized at $j=255$, when the ratio is $1/127$. Consequently, by the
pigeonhole principle, there is a pseudoline that receives at least

$\frac{9.637}{64}n^{2}\cdot\frac{1}{127}\cdot\frac{1}{n}\geq\frac{n}{845}$

credits, i.e., has at least this number of crossing points, as required. ∎

The resemblance of the argument in the proof of Theorem 8 with the following
result of Beck [5] is worth noting.

######  Theorem 11.

(Beck [5]). There is constant $c>0$ such that for any set $S$ of $n$ points in
the plane, either

  1. ($\alpha$)

some line contains at least $cn$ points of $S$, or

  2. ($\beta$)

the number of distinct lines determined by $S$ is at least $cn^{2}$.

In general one cannot guarantee the existence of more pseudolines with the
property in Theorem 8. Indeed, consider the $n$-sequence of permutations:

$1,2,\ldots,n-1,n\xrightarrow{1,2,\ldots,n-1}n-1,n-2,\ldots,2,1,n\xrightarrow{1,n}n-1,n-2,\ldots,2,n,1\xrightarrow{}\cdots\xrightarrow{}n,n-1,\ldots,2,1.$

The only pseudoline whose local sequence is of length $\Omega(n)$ is the $n$th
one. However, under very mild conditions, the stronger statement in Theorem 9
is in effect. Its proof is analogous to that of Theorem 8.

### Proof of Theorem 9 (sketch).

Assume first that there exists a $k$-rich crossing point $\xi$ for $k=cn$, for
some positive constant $c\leq\delta$. Consider the subset of pseudolines
$\mathcal{L}^{\prime}\subset\mathcal{L}$ involved in this crossing. We have
$cn\leq|\mathcal{L}^{\prime}|\leq\delta n$. By Observation 1, for every
pseudoline $\ell\in\mathcal{L}\setminus\mathcal{L}^{\prime}$, the length of
$\ell$’s local sequence is at least $cn$. Moreover,
$|\mathcal{L}\setminus\mathcal{L}^{\prime}|\geq(1-\delta)n$, as required.

If there is no $k$-rich crossing point for $k=cn$, for a sufficiently small
$c>0$, the proof is finished as before, by obtaining an $\Omega(n^{2})$ lower
bound analogous to (2). We omit the details. ∎

It should be noted that Theorem 9 is a dual extension of Beck’s result
mentioned above.

##  4 Upper bound questions and concluding remarks

In this section we prove Theorem 10. In $2014$, Lund, Purdy, and Smith [39]
demonstrated an infinite family of (nontrivial) pseudoline arrangements, in
which an arrangement of $n$ pseudolines has no member incident to more than
$4n/9$ points of intersection (i.e., vertices of the arrangement), and thereby
showed that the strong Dirac conjecture does not hold for pseudolines. One
feature of the respective family of arrangements is that they contain vertices
with high incidence, in particular, about $n/3$ pseudolines are incident to a
single vertex. The authors asked the following.

######  Question 1.

(Lund, Purdy, and Smith [39]) Is there an infinite family of arrangements of
$n$ pseudolines, such that

  * •

no vertex is incident to $\Omega(n)$ pseudolines, and

  * •

no pseudoline is incident to more than $(1-\varepsilon)\,\frac{n}{2}$
vertices, for some constant $\varepsilon>0$?

The authors further relaxed the second requirement by replacing
$(1-\varepsilon)\,\frac{n}{2}$ with $cn$, where $c<1$ is a constant, and asked
for such an arrangement. Here we give a positive answer to the latter
question, while we show that the first requirement can be substantially
strengthened in that case. Interestingly enough, the best construction we
found uses straight lines as we were not able to exploit the power of curved
pseudolines. The features of the construction are described in Theorem 10. It
is worth noting, however, that this construction falls short of answering
Question 1.

### The deltoid construction.

The construction can be traced back to Rigby [50] who provided an analysis,
and even further back; for instance, an illustration can be found in [38, Ch.
8]. This line arrangement has been also used in [6, 25], where descriptions
and useful properties can be found. Let $\ell(\theta)$ denote the line
connecting $e^{i\theta}$ and $e^{i(\pi-2\theta)}$ on the unit circle, with the
understanding that $\ell(\theta)$ is the tangent line when the two points
coincide. We take the freedom to denote the construction in this way based on
the fact that $\ell(\theta)$ envelops a _deltoid_ as $\theta$ varies. Its key
property stems from the following.

######  Lemma 3.

(Rigby [50], Füredi and Palásti [25]). The lines $\ell(\alpha)$,
$\ell(\beta)$, and $\ell(\gamma)$ are concurrent if and only if
$\alpha+\beta+\gamma\equiv 0\pmod{2\pi}$.

Figure 4: The deltoid construction for $n=18$ lines.

Consider a regular $n$-gon inscribed in the unit circle centered at the
origin, where $n$ is even, and refer to Fig. 4. Let
$p_{0},p_{1},\ldots,p_{n-1}$ denote its vertices labeled counterclockwise
starting from $p_{0}=(1,0)$. For $i=0,1,\ldots,n-1$, draw the lines connecting
$p_{i}$ with $p_{n/2-2i}$, where indices are considered modulo $n$. If the
points $p_{i}$ and $p_{n/2-2i}$ coincide, draw the tangent line to the circle
at $p_{i}$. The resulting arrangement has $n$ lines,
$1+\left\lceil\frac{n(n-3)}{6}\right\rceil$ triple points (i.e., vertices
incident to $3$ lines), and $n-3+\delta(n)$ double points (i.e., ordinary
vertices), where $\delta(n)=0$ if $n\equiv 0\pmod{3}$ and $\delta(n)=2$
otherwise; see, e.g., [6]. Moreover, double points may only appear on the
outer envelope, whence each line is incident to at most $3$ double points, and
Theorem 10 follows. Obviously, the constant $1/2$ in the theorem is the best
possible (for lines or pseudolines) under the first constraint.

Determining the right constant in Conjecture 2 remains an interesting open
problem. It is easy to obtain small improvements in the lower bound by
slightly adjusting the parameters in the proof of Theorem 8. Since we suspect
that the answer is much closer to the best known upper bound of Lund, Purdy
and Smith, we did not insist in that direction.

## References

  * [1] Eyal Ackerman, On topological graphs with at most four crossings per edge, _Computational Geometry: Theory and Applications_ 85 (2019), article 101574.
  * [2] Martin Aigner and Günter M. Ziegler, _Proofs from the Book_ , 6th edition, Springer, Berlin, 2018.
  * [3] Miklós Ajtai, Vašek Chvátal, Monroe M. Newborn, and Endre Szemerédi, Crossing-free subgraphs, _Annals of Discrete Mathematics_ 12 (1982), 9–12.
  * [4] Jin Akiyama, Hiro Ito, Midori Kobayashi, and Gisaku Nakamura, Arrangements of $n$ points whose incident-line-numbers are at most $n/2$, _Graphs and Combinatorics_ 27(3) (2011), 321–326.
  * [5] József Beck, On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry, _Combinatorica_ 3 (1983), 281–297.
  * [6] Jürgen Bokowski and Piotr Pokora, On the Sylvester–Gallai and the orchard problem for pseudoline arrangements, _Periodica Mathematica Hungarica_ 77(2) (2018), 164–174.
  * [7] Peter Borwein and William O. J. Moser, A survey of Sylvester’s problem and its generalizations, _Aequationes Mathematicae_ 40(1) (1990), 111–135.
  * [8] Peter Braß, William Moser, and János Pach, _Research Problems in Discrete Geometry_ , Springer, New York, 2005.
  * [9] Don Chakerian, Sylvester’s problem on collinear points and a relative, _The American Mathematical Monthly_ 77(2) (1970), 164–167.
  * [10] Vašek Chvátal, _The Discrete Mathematical Charms of Paul Erdős_ , Cambridge University Press, New York, 2021.
  * [11] Hallard T. Croft, Kenneth J. Falconer, and Richard K. Guy, _Unsolved Problems in Geometry_ , Springer, New York, 1991.
  * [12] Gabriel A. Dirac, Collinearity properties of sets of points, _The Quarterly Journal of Mathematics_ 2(1) (1951), 221–227.
  * [13] Adrian Dumitrescu and Csaba D. Tóth, Distinct triangle areas in a planar point set, _Proc. 12th Conference on Integer Programming and Combinatorial Optimization_ (IPCO 2007), vol. 4513 of LNCS, Springer, pp. 119–129.
  * [14] Herbert Edelsbrunner, _Algorithms in Combinatorial Geometry_ , Springer, Berlin, 1987.
  * [15] Herbert Edelsbrunner and Emo Welzl, On the number of line separations of a finite set in the plane, _Journal of Combinatorial Theory, Series A_ 38(1) (1985), 15–29.
  * [16] Paul Erdős, Three point collinearity, _American Mathematical Monthly_ 50 (1943), 65.
  * [17] Paul Erdős, Some unsolved problems, _Publ. Math. Inst. Hungar. Acad. Sci._ 6 (1961), 221–254.
  * [18] Nicolaas G. de Bruijn and Paul Erdős, On a combinatorial problem, _Proc. Kon. Ned. Akad. v. Wetensch._ 51 (1948), 1277–1279.
  * [19] Paul Erdős and George Purdy, Extremal problems in combinatorial geometry, in _Handbook of Combinatorics_ (vol. 1), (Ronald Graham, László Lovász, and Martin Grötschel, editors), Elsevier, 1995, pp. 809–874.
  * [20] Paul Erdős and György Szekeres, A combinatorial problem in geometry, _Compositio Mathematica_ 2 (1935), 463–470.
  * [21] Paul Erdős and György Szekeres, On some extremum problems in elementary geometry, _Annales Universitatis Scientiarium Budapestinensis de Rolando Eötvös Nominatae Sectio Mathematica_ 3-4 (1960), 53–62.
  * [22] Stefan Felsner, _Geometric Graphs and Arrangements_ , Advanced Lectures in Mathematics, Vieweg Verlag, 2004.
  * [23] Stefan Felsner and Jacob E. Goodman, Pseudoline arrangements, in _Handbook of Discrete and Computational Geometry_ (3rd edition), (J. E. Goodman, J. O’Rourke, C. D. Tóth, editors), CRC Press, Boca Raton, 2017, pp. 125–157.
  * [24] Stefan Felsner and Pavel Valtr, Coding and counting arrangements of pseudolines, _Discrete & Computational Geometry_ 46(4) (2011), 405–416.
  * [25] Zoltán Füredi and Ilona Palásti, Arrangements of lines with a large number of triangles, _Proceedings of the American Mathematical Society_ 92(4) (1984), 561–566.
  * [26] Jacob E. Goodman and Richard Pollack, On the combinatorial classification of nondegenerate configurations in the plane, _Journal of Combinatorial Theory Ser. A_ 29 (1980), 220–235.
  * [27] Jacob E. Goodman and Richard Pollack, A combinatorial perspective on some problems in geometry, _Congressus Numerantium_ 32 (1981), 383–394.
  * [28] Jacob E. Goodman and Richard Pollack, Allowable sequences and order types in discrete and computational geometry. in _New Trends in Discrete and Computational Geometry_ (János Pach, editor), Algorithms and Combinatorics, Volume 10, Springer, New York, 1993, pp. 103–134.
  * [29] Ben Green and Terence Tao, On sets defining few ordinary lines, _Discrete & Computational Geometry_ 50(2) (2013), 409–468.
  * [30] Branko Grünbaum, _Arrangements and Spreads_ , Amer. Math. Soc., Providence, 1972.
  * [31] Zeye Han, A Note on the weak Dirac conjecture, _Electron. J. Comb._ 24(1) (2017), #P1.63.
  * [32] Andreas Holmsen, Hossein N. Mojarrad, János Pach, and Gábor Tardos, Two extensions of the Erdős–Szekeres problem, _Journal of the European Mathematical Society_ 22(12) (2020), 3981–3995.
  * [33] Leroy M. Kelly and William O. J. Moser, On the number of ordinary lines determined by $n$ points, _Canadian Journal of Mathematics_ 10 (1958), 210–219.
  * [34] Victor Klee and Stan Wagon, _Old and New Unsolved Problems in Plane Geometry and Number Theory_ , Mathematical Association of America, Washington, DC, 1991.
  * [35] Donald E. Knuth, _Axioms and Hulls_ , Lecture Notes in Computer Science, Vol. 606, Springer, Berlin, 1992.
  * [36] Thomas Leighton, New lower bound techniques for VLSI, _Math. Systems Theory_ 17 (1984), 47–70.
  * [37] Jacobus H. van Lint and Richard M. Wilson, _A Course in Combinatorics_ , Cambridge University Press, 2nd edition, New York, 2001.
  * [38] Edward H. Lockwood, _A Book of Curves_ , Cambridge University Press, 1961.
  * [39] Ben Lund, George B. Purdy, and Justin W. Smith, A Pseudoline counterexample to the strong Dirac conjecture, _Electron. J. Comb._ 21(2) (2014), #P2.31.
  * [40] Theodore S. Motzkin, The lines and planes connecting the points of a finite set, _Transactions of the American Mathematical Society_ 70(3) (1951), 451–464.
  * [41] Theodore S. Motzkin, Nonmixed connecting lines. Abstract 67T 605, _Notices Amer. Math. Soc_ 14 (1967), 837.
  * [42] Theodore S. Motzkin, Sets for which no point lies on many connecting lines, _Journal of Combinatorial Theory, Series A_ 18(3) (1975), 345–348.
  * [43] Niranjan Nilakantan, Extremal problems related to the Sylvester–Gallai theorem, in _Combinatorial and Computational Geometry_ (Jacob E. Goodman, János Pach, Emo Welzl, editors), MSRI Publications, Volume 52, 2005, pp. 479–494.
  * [44] János Pach, Directions in combinatorial geometry, _Jahresbericht der Deutschen Mathematiker-Vereinigung_ 107 (2005), 215–225.
  * [45] János Pach, Radoš Radoičić, Gábor Tardos, and Géza Tóth, Improving the crossing lemma by finding more crossings in sparse graphs, _Discrete & Computational Geometry_ 36(4) (2006), 527–552.
  * [46] János Pach and Micha Sharir, _Combinatorial Geometry and Its Algorithmic Applications—The Alcalá Lectures_ , Mathematical Surveys and Monographs, Vol. 152, American Mathematical Society, Providence, RI, 2009.
  * [47] Michael S. Payne, _Combinatorial Geometry of Point Sets with Collinearities_ , PhD thesis, The University of Melbourne, Dept. of Mathematics and Statistics, 2014.
  * [48] Michael S. Payne and David R. Wood, Progress on Dirac’s conjecture, _Electron. J. Comb._ 21(2) (2014), #P2.12.
  * [49] Hoang Ha Pham and Tien Cuong Phi, A new progress on weak Dirac conjecture, preprint, 2016, arXiv:1607.08398.
  * [50] John F. Rigby, Multiple intersections of diagonals of regular polygons, and related topics, _Geometriae Dedicata_ 9(2) (1980), 207–238.
  * [51] Andrew Suk, On the Erdős–Szekeres convex polygon problem, _Journal of the American Mathematical Society_ 30 (2017), 1047–1053.
  * [52] James Joseph Sylvester, Mathematical question 11851, _Educational Times_ 46 (1893), 156.
  * [53] László Székely, Crossing numbers and hard Erdős problems in discrete geometry, _Combinatorics, Probability and Computing_ 6 (1997), 353–358.
  * [54] Endre Szemerédi and William T. Trotter, Extremal problems in discrete geometry, _Combinatorica_ 3 (1983), 381–392.
  * [55] Peter Ungar, $2N$ noncollinear points determine at least $2N$ directions, _Journal of Combinatorial Theory Ser. A_ 33 (1982), 343–347.


# The case for evaluating multimodal translation models on text datasets

Vipin Vijayan${}^{\text{1}}$, Braeden Bowen${}^{\text{1}}$, Scott
Grigsby${}^{\text{1}}$, Timothy Anderson${}^{\text{2}}$, Jeremy
Gwinnup${}^{\text{2}}$
${}^{\text{1}}$PAR Government Systems Corporation, ${}^{\text{2}}$Air Force
Research Laboratory
{vipin_vijayan, braeden_bowen<EMAIL_ADDRESS>
{timothy.anderson.20<EMAIL_ADDRESS>
###### Abstract

A good evaluation framework should evaluate multimodal machine translation
(MMT) models by measuring 1) their use of visual information to aid in the
translation task and 2) their ability to translate complex sentences such as
done for text-only machine translation. However, most current work in MMT is
evaluated against the Multi30k testing sets, which do not measure these
properties. Namely, the use of visual information by the MMT model cannot be
shown directly from the Multi30k test set results and the sentences in
Multi30k are are image captions, i.e., short, descriptive sentences, as
opposed to complex sentences that typical text-only machine translation models
are evaluated against.

Therefore, we propose that MMT models be evaluated using 1) the CoMMuTE
evaluation framework, which measures the use of visual information by MMT
models, 2) the text-only WMT news translation task test sets, which evaluates
translation performance against complex sentences, and 3) the Multi30k test
sets, for measuring MMT model performance against a real MMT dataset. Finally,
we evaluate recent MMT models trained solely against the Multi30k dataset
against our proposed evaluation framework and demonstrate the dramatic drop
performance against text-only testing sets compared to recent text-only MT
models.

The case for evaluating multimodal translation models on text datasets

Vipin Vijayan${}^{\text{1}}$, Braeden Bowen${}^{\text{1}}$, Scott
Grigsby${}^{\text{1}}$, Timothy Anderson${}^{\text{2}}$, Jeremy
Gwinnup${}^{\text{2}}$ ${}^{\text{1}}$PAR Government Systems Corporation,
${}^{\text{2}}$Air Force Research Laboratory {vipin_vijayan, braeden_bowen,
<EMAIL_ADDRESS>{timothy.anderson.20<EMAIL_ADDRESS>

##  1 Introduction

Multimodal machine translation (MMT) is the problem of automatically
translating text from one language to another with the aid of additional
modalities such as image, video, audio. The hypothesis that contextually
relevant images would help resolve ambiguities or missing information in
machine translation (MT) is persuasive. For example, the word bank in English
can mean financial institutions or river banks, which typically are
unambiguously different words in other languages. A practical use for MMT is
improved translations of closed captioning or subtitles in videos.

Much work in MMT focus on the Multi30k dataset (Elliott et al., 2016), a
dataset comprising 30,014 image captions and corresponding translations in
different languages. Introduced alongside the WMT 2016 Multimodal Translation
task, the dataset has sparked a series of papers in multimodal machine
translation (Huang et al., 2016; Calixto and Liu, 2017; Caglayan et al., 2017;
Yao and Wan, 2020; Yin et al., 2020; Wu et al., 2021; Li et al., 2022).

###  1.1 Evaluating MMT models

MMT models are typically evaluated against the Multi30k test sets, which also
comprise of image captions and corresponding translations. It has been
suggested before that the Multi30k test sets are not adequate for evaluating
MMT models since 1) many MMT models do not make use of the visual context
(Caglayan et al., 2019) and reported performance improvements reported were
due to the regularization effect that come from treating the multimodal data
as random noise (Wu et al., 2021), 2) the use of visual information by the MMT
model cannot be shown directly from the test set results, 3) the image
captions are short, descriptive sentences as opposed to complex sentences
present in text-only MT evaluation datasets, and 4) most of the captions do
not require the image in order to be correctly translated due to the captions
being unambiguous (Futeral et al., 2023). In this work, we also show that MMT
models trained against the Multi30k dataset perform poorly against testing
sets used by typical text-only translation models.

There have been previous work in improving the evaluation methodology for MMT.
Recently, Futeral et al. (2023) proposed an evaluation framework, CoMMuTE
(Contrastive Multilingual Multimodal Translation Evaluation), where the
authors evaluate how well an MMT model can use visual information to perform
the translation task. The challenge in this evaluation for the MMT model is,
given a lexically ambiguous sentence in English, and a translation of the
ambiguous sentence that fits one of two images, determine from which of the
two images the English sentence and its translation fits best. The
determination is made by selecting the input text and image pair with lower
perplexity of the output. The final CoMMuTE score is calculated using the
average accuracy over all of the ambiguous sentence and image pairs. While
CoMMuTE is useful for measuring how well the MMT model uses visual
information, the sentences present do not represent the complexity present in
text-only evaluation sets.

Our desired goal in MMT is to translate complex sentences, such as is done in
typical machine translation, with the aid of contextual image information.
However, most current work in MMT focus on the Multi30k dataset and other
small MMT datasets (e.g., VATEX (Wang et al., 2020)), which are typically
captions, i.e., short sentences describing the images or videos, along with
respective translations. Since many MMT models train only against the Multi30k
datasets, this results in overfitted models that have no practical use in the
real world. While ideally there would be a test dataset containing complex
sentences with ambiguities that can be resolve with contextual image
information, we can use the WMT news translation task test sets (Kocmi et al.,
2022), which contain complex sentences from news media, and are used as a
standard in text-only machine translation, along with the CoMMuTE framework,
which informs us whether the model uses image information as a proxy for such
a testing set.

###  1.2 Proposal

A good evaluation framework should evaluate MMT models by measuring 1) their
use of visual information to aid in the translation task and 2) their ability
to translate complex sentences such as is done for text-only machine
translation.

Thus, to evaluate along both of these axes, we propose that MMT models be
evaluated using 1) the CoMMuTE evaluation framework Futeral et al. (2023),
which measures the use of visual information by MMT models, 2) the text-only
WMT news translation task test sets, which evaluates translation performance
against complex sentences, and 3) the Multi30k test sets, for measuring MMT
model performance against a real MMT dataset.

Performing well against all three of these evaluation measures is a
significantly more difficult task than performing well against the Multi30k
test sets alone. As we show in our work, simply training the model against the
Multi30k dataset will not result in good performance against all three
metrics.

###  1.3 Our contributions

  * •

We design an evaluation framework that takes into consideration the ability of
MMT models to 1) use visual information to aid in the translation task and 2)
translate complex sentences like typical text-only MT models.

  * •

We show that while MMT models trained solely against the Multi30k training set
perform well against the Multi30k test sets, the models perform very poorly
against the WMT news translation task test sets.

##  2 Related Works

As discussed in Section 1.1, there has been many works on evaluation of MMT
models. Here, we focus on the MMT models and datasets we evaluate in this
work.

Wu et al. (2021) discovered the improvements achieved by the multimodal models
over text-only counterparts are in fact results of the regularization effect
since the models learn to ignore the multimodal information. They introduced
two interpretable MMT models, Gated Fusion and RMMT, and performed non-
matching evaluation on their models (by inputting random images instead of
contextual images with the source text) and showed that adding model
regularization achieves results that are comparable to incorporating visual
context.

Futeral et al. (2023) focused on the challenge of resolving ambiguity in the
source text by using contextual images for MMT. They proposed an MMT model
that combines the standard MMT objective with a visually-conditioned masked
language modeling (VMLM) objective (Li et al., 2020; Lu et al., 2019; Su et
al., 2020). They showed that their model was able to successfully translate
ambiguous source text into unambiguous output text while using the input image
as context. Importantly, they introduced the CoMMuTE evaluation framework to
demonstrate that the model can successfully disambiguate the source text and
use vision information to perform the translation task. We use the CoMMuTE
framework as part of our proposed evaluation framework.

##  3 Methods

###  3.1 Proposed evaluation framework

As discussed in Section 1, we evaluate using 1) the CoMMuTE evaluation
framework, 2) the WMT news translation task test sets, and 3) the Multi30k
test sets.

Input: Get away from the float!
---
|
Ref: Veg vom Schwimmer! | Ref: Veg vom Festwagen!
Figure 1: Example ambiguous English sentence, contextual images, and
unambiguous non-English reference sentences from the CoMMuTE test dataset.

####  3.1.1 CoMMuTE

The CoMMuTE framework (Futeral et al., 2023) evaluates how well the MMT model
can use visual information to perform the translation task. The CoMMuTE
testing set contains 50 lexically ambiguous English sentences, where each
sentence is associated with two images that disambiguate the English sentence
into two non-English sentences (Figure 1).

For each ambiguous English sentence and associated image pair, the challenge
in this evaluation framework for the MMT model is to select which of the two
non-English sentences matches up best with the English sentence-image pair.

The determination is made by calculating the perplexity of the (English
sentence, image, non-English sentence) triplet using the MMT model. This is
done for the two non-English sentences. Then, the non-English sentence with
the lower perplexity is selected as the correct translation. The final CoMMuTE
score is calculated using the average accuracy over all of the 100 ambiguous
English sentence and image pairs.

####  3.1.2 WMT news translation task test sets

The WMT news translation task test sets (newstest) have been used in the WMT
machine translation task for many years (Kocmi et al., 2022). The newstest
test sets consists of sentences taken from news media, where the sentences
range from two words to 170 words (for the English sentences). Each year, the
WMT challenge evaluates translation models against a newstest test set for
that particular year and release the past year’s translations. In this work,
since the FAIR-WMT19 model that we compare against was trained on newstest
test sets from years 2018 and prior, we evaluate against newstest test sets
from years 2019 (1,997 sentences) and 2020 (1,418 sentences) using BLEU4.

####  3.1.3 Multi30k

The Multi30k dataset was introduced alongside the WMT 2016 multimodal
translation task, which introduced the task of MMT. The Multi30k dataset
contains 29,000 training images and 1,014 validation images with parallel
sentences in English and German. The Multi30k images are from the Flickr30k
dataset (Young et al., 2014) with the German translations created by
professional translators from the original English image descriptions.

We evaluate against the Multi30k Test2016 test set (1000 examples) and the
Test2017 test set (1000 examples) using BLEU4.

###  3.2 MMT models

We evaluate the Gated Fusion and RMMT multimodal translation models proposed
by Wu et al. (2021) that performs well against the Multi30k test sets, and
compare the results against the FAIR-WMT19 (Ng et al., 2019) text-only
translation model.

The Gated Fusion model is a conventional Transformer-based (Vaswani et al.,
2017) MMT model which takes as input the source text and the image. It
contains learnable gating matrices that integrate the multimodal information
while allowing for interpretability in terms how the model weighs text and
image information to produce its output.

The RMMT method is a Transformer-based retrieval-augmented model which takes
as input only the source text. It uses the source text to retrieve
contextually relevant images to aid in producing its output.

For comparison, we also report the performance results achieved by Futeral et
al. (2023), where they introduced the CoMMuTE framework and their VGAMT model.
The VGAMT method is a conventional Transformer-based MMT model that was
trained using visually-conditioned masked language modeling (VMLM).

For the Gated Fusion model, we evaluate against the Multi30k test sets as was
done in their work. We also evaluate against the Multi30k test sets and
newstest test sets in a non-matching manner, that is, by associating random
images in the Multi30k dataset to each sentence. For the RMMT model, we use
the source text as input and the image retrieval query as done in their work.

Since we are evaluating against trained models, we perform the respective pre-
processing required for the trained models. For the Gated Fusion and RMMT
models, we lowercase, normalize punctuation, tokenize, and perform BPE
encoding using the moses tokenizer and subword-nmt. For the RMMT model, we use
the lowercased and tokenized source text for the retrieval query as was done
in their work. Similarly for the FAIR-WMT19 model, we perform the tokenization
and BPE encoding pre-processing steps done by Ng et al. (2019).

Label | CoMMuTE | Multi30k | newstest
---|---|---|---
|  | 2016 | 2017 | 2019 | 2020
| Score | BLEU4
Multimodal inputs
Gated Fusion | 0.50 | 42.0 | 33.6 |
VGAMT | 0.59 | 43.3 | 38.3 |
Text inputs only
FAIR-WMT19 | 0.50 | 40.7 | 37.7 | 40.6 | 36.2
RMMT | 0.50 | 41.5 | 33.0 | 1.3 | 0.8
Non-matching inputs
Gated Fusion | 0.50 | 42.0 | 33.6 | 1.3 | 0.6
Table 1: BLEU4 scores against the Multi30k test sets and the newstest test
sets as well as CoMMuTE scores for English to German translations (en-de).
Performance of the Gated Fusion and RMMT models (Wu et al., 2021) trained
against the Multi30k dataset is shown. The results of the FAIR-WMT19 (Ng et
al., 2019) text-only model is shown for comparison.

##  4 Results and Discussion

Since both the Gated Fusion and RMMT models are trained solely against the
Multi30k dataset, we expect there to be a drop in performance when evaluating
against out-of-domain testing sets such as the newstest test sets. As shown in
Table 1, while the two models perform well against the Multi30k test sets, we
found the drop in performance against the newstest test sets to be very large,
making the two models impractical for real-world usage.

Specifically, for the Gated Fusion model, we found performance to be identical
no matter which image was associated with the sentence, which indicates that
the model is not be using image information to a significant degree. The fact
that the Gated Fusion model learns to ignore image information was discussed
by Wu et al. (2021). Furthermore, while the Gated Fusion method performed
comparably against the FAIR-WMT19 model on the Multi30k test sets, we see that
there is a drastic loss of performance when evaluated against the newstest
test sets.

For the RMMT model, we use the source text as the retrieval query for the
image retrieval, as was done in the original paper. Similar to the Gated
Fusion method, there is a drastic loss of performance when evaluated against
the newstest test sets.

We theorize that the primary reasons for this drastic drop in performance are
1) domain mismatch between the image captions in the Multi30k dataset compared
to the longer, more complex newstest test sets, 2) the difference in lengths
in the input sentences between the newstest test sets and the Multi30k
training set (e.g., the average number of words per example in both the
Multi30k training set and the Multi30k test2016 is 12 while it is 34 in
newstest2020), 3) the difference in vocabulary between the newstest test sets
and the Multi30k training set (e.g., out of approximately 8200 unique words in
newstest2020, 5280 words are not in Multi30k training set, while out of
approximately 1890 unique words in Multi30k test2016, only 140 words are not
in the Multi30k training set), and 4) overfitting on the very small Multi30k
training set via both the training process and the BPE pre-processing (29,000
examples).

00footnotetext:  Opinions, interpretations, conclusions, and recommendations
are those of the authors and are not necessarily endorsed by the United States
Government. Cleared for public release on 12 Feb 2024. Originator reference
number RH-24-125350. Case number AFRL-2024-0794.

##  5 Conclusion

Multimodal translation models are typically trained against the Multi30k
dataset or a dataset containing relatively few number of captions. However,
practical machine translation requires that models be able to translate
complex sentences with contextual image information. Using this principle, we
introduce an evaluation framework for MMT models that 1) measures their use of
visual information to aid in the translation task and 2) measures their
ability to translate complex sentences such as done for text-only MT.

We also show that while current models trained against the Multi30k dataset
may perform well against the Multi30k testing sets, they can perform poorly
against other testing sets used to evaluate text-only models. This calls for a
need to evaluate against these testing sets in the MMT domain.

Our results on current MMT models also suggest that MMT models be designed and
trained in such a way that they have a baseline high performance on text-only
translation. For future work, we plan to adapt a text-only MT model to MMT and
then fine-tune the MMT model while retaining its text-only translation
performance.

## Acknowledgements

This work is sponsored by the Air Force Research Laboratory under Air Force
contract FA8650-20-D-6207.

## References

  * Caglayan et al. (2017) Ozan Caglayan, Walid Aransa, Adrien Bardet, Mercedes García-Martínez, Fethi Bougares, Loïc Barrault, Marc Masana, Luis Herranz, and Joost van de Weijer. 2017\.  LIUM-CVC Submissions for WMT17 Multimodal Translation Task.  In _Proceedings of the Second Conference on Machine Translation_ , pages 432–439, Copenhagen, Denmark. Association for Computational Linguistics.
  * Caglayan et al. (2019) Ozan Caglayan, Pranava Madhyastha, Lucia Specia, and Loïc Barrault. 2019.  Probing the Need for Visual Context in Multimodal Machine Translation.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4159–4170, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Calixto and Liu (2017) Iacer Calixto and Qun Liu. 2017.  Incorporating global visual features into attention-based neural machine translation. In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 992–1003, Copenhagen, Denmark. Association for Computational Linguistics.
  * Elliott et al. (2016) Desmond Elliott, Stella Frank, Khalil Sima’an, and Lucia Specia. 2016.  Multi30K: Multilingual English-German Image Descriptions.  In _Proceedings of the 5th Workshop on Vision and Language_ , pages 70–74. Association for Computational Linguistics.  Event-place: Berlin, Germany.
  * Futeral et al. (2023) Matthieu Futeral, Cordelia Schmid, Ivan Laptev, Benoît Sagot, and Rachel Bawden. 2023.  Tackling ambiguity with images: Improved multimodal machine translation and contrastive evaluation.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 5394–5413, Toronto, Canada. Association for Computational Linguistics.
  * Huang et al. (2016) Po-Yao Huang, Frederick Liu, Sz-Rung Shiang, Jean Oh, and Chris Dyer. 2016.  Attention-based multimodal neural machine translation.  In _Proceedings of the First Conference on Machine Translation: Volume 2, Shared Task Papers_ , pages 639–645, Berlin, Germany. Association for Computational Linguistics.
  * Kocmi et al. (2022) Tom Kocmi, Rachel Bawden, Ondřej Bojar, Anton Dvorkovich, Christian Federmann, Mark Fishel, Thamme Gowda, Yvette Graham, Roman Grundkiewicz, Barry Haddow, Rebecca Knowles, Philipp Koehn, Christof Monz, Makoto Morishita, Masaaki Nagata, Toshiaki Nakazawa, Michal Novák, Martin Popel, and Maja Popović. 2022.  Findings of the 2022 conference on machine translation (WMT22).  In _Proceedings of the Seventh Conference on Machine Translation (WMT)_ , pages 1–45, Abu Dhabi, United Arab Emirates (Hybrid). Association for Computational Linguistics.
  * Li et al. (2020) Liunian Harold Li, Mark Yatskar, Da Yin, Cho-Jui Hsieh, and Kai-Wei Chang. 2020\.  What does BERT with vision look at? In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 5265–5275, Online. Association for Computational Linguistics.
  * Li et al. (2022) Y. Li, R. Panda, Y. Kim, C. Chen, R. Feris, D. Cox, and N. Vasconcelos. 2022.  Valhalla: Visual hallucination for machine translation.  In _2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 5206–5216, Los Alamitos, CA, USA. IEEE Computer Society.
  * Lu et al. (2019) Jiasen Lu, Dhruv Batra, D. Parikh, and Stefan Lee. 2019.  ViLBERT: Pretraining Task-Agnostic Visiolinguistic Representations for Vision-and-Language Tasks.  In _NeurIPS_.
  * Ng et al. (2019) Nathan Ng, Kyra Yee, Alexei Baevski, Myle Ott, Michael Auli, and Sergey Edunov. 2019\.  Facebook FAIR’s WMT19 news translation task submission.  In _Proceedings of the Fourth Conference on Machine Translation (Volume 2: Shared Task Papers, Day 1)_ , pages 314–319, Florence, Italy. Association for Computational Linguistics.
  * Su et al. (2020) Weijie Su, Xizhou Zhu, Yue Cao, Bin Li, Lewei Lu, Furu Wei, and Jifeng Dai. 2020\.  VL-BERT: Pre-training of Generic Visual-Linguistic Representations.  In _International Conference on Learning Representations_.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc.
  * Wang et al. (2020) Xin Wang, Jiawei Wu, Junkun Chen, Lei Li, Yuan-Fang Wang, and William Yang Wang. 2020.  _VATEX: A Large-Scale, High-Quality Multilingual Dataset for Video-and-Language Research_.  _eprint: 1904.03493.
  * Wu et al. (2021) Zhiyong Wu, Lingpeng Kong, Wei Bi, Xiang Li, and Ben Kao. 2021.  Good for misconceived reasons: An empirical revisiting on the need for visual context in multimodal machine translation.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 6153–6166, Online. Association for Computational Linguistics.
  * Yao and Wan (2020) Shaowei Yao and Xiaojun Wan. 2020.  Multimodal Transformer for Multimodal Machine Translation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4346–4350, Online. Association for Computational Linguistics.
  * Yin et al. (2020) Yongjing Yin, Fandong Meng, Jinsong Su, Chulun Zhou, Zhengyuan Yang, Jie Zhou, and Jiebo Luo. 2020.  A Novel Graph-based Multi-modal Fusion Encoder for Neural Machine Translation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 3025–3035, Online. Association for Computational Linguistics.
  * Young et al. (2014) Peter Young, Alice Lai, Micah Hodosh, and Julia Hockenmaier. 2014.  From image descriptions to visual denotations: New similarity metrics for semantic inference over event descriptions.  _Transactions of the Association for Computational Linguistics_ , 2:67–78.