#  Positive Geometries for Barycentric Interpolation

Márton Vaitkus  Budapest University of Technology and Economics

###### Abstract

We propose a novel theoretical framework for barycentric interpolation, using
concepts recently developed in mathematical physics. Generalized barycentric
coordinates are defined similarly to Shepard’s method, using positive
geometries – subsets which possess a rational function naturally associated to
their boundaries. Positive geometries generalize certain properties of
simplices and convex polytopes to a large variety of geometric objects. Our
framework unifies several previous constructions, including the definition of
Wachspress coordinates over polytopes in terms of adjoints and dual polytopes.
We also discuss potential applications to interpolation in 3D line space,
mean-value coordinates and splines.

## 1 Overview

The interpolation of scalar- or vector-valued data is an important task in
many fields, including numerical analysis, geometric modeling and computer
graphics. _Barycentric coordinates_ can be defined over segments, triangles
and simplices as well as more complex shapes, such as polytopes [4]. These
include _Wachspress coordinates_ [17] which are rational functions defined for
convex polytopes. Wachspress coordinates were also generalized to subsets
bounded by non-linear hypersurfaces [2] and can be defined in several
equivalent ways [18, 11, 9]. We describe a theoretical framework that
clarifies the relationship between these different formulations, and provides
opportunities for novel generalizations.

We propose a set of basic building blocks for barycentric interpolation
methods: _positive geometries_. Positive geometries have been recently
introduced in the theoretical physics literature [1], but their application to
interpolation problems has not been explored before. Besides simplices and
polytopes, the category of positive geometries includes objects with similar
combinatorial properties, such as polycons [17] or “positive” parts of toric
varieties [15] and Grassmannians [12, 6]. A positive geometry carries a
“canonical” differential form: a rational function with the properties of a
signed volume, that has its poles (where the denominator vanishes) along the
boundaries of the “positive” region. Crucially, these poles have a recursive
structure, i.e. restricting a canonical form to a boundary component (via a
generalization of taking complex residues) results in another canonical form.
Thus, positive geometries share many properties with polytopes – most
importantly, that complicated objects can be constructed by adding together
simpler ones. To define interpolation in terms of canonical forms, we use a
variant of Shepard’s method [4, 13]: barycentric coordinates are ratios
tending to $\frac{\infty}{\infty}$ along the interpolated boundaries. For
polytopes, our construction recovers the definition of Wachspress coordinates
in terms of dual volumes [9].

In this preliminary work, our goal is to introduce the theory of positive
geometries to our audience, and demonstrate how they generalize earlier
constructions for barycentric interpolation. After some motivating
observations (Section 2), we give a definition of positive geometries and
their canonical forms, also giving some examples (Section 3). We then describe
how to use the canonical forms of positive geometries for barycentric
interpolation (Section 4). Finally, we discuss potential applications of this
framework to interpolation in line space, and possible extensions to non-
rational barycentric coordinates and splines (Section 5).

## 2 Motivation

Let us consider the basic example of linear interpolation over a segment
$[a,b]\subset\mathbb{R}$. The standard formula

$\displaystyle f(x)=\frac{b-x}{b-a}f(a)+\frac{x-a}{b-a}f(b),$ (2.1)

can be written in an alternative _barycentric form_ [8]:

$\displaystyle
f(x)=\frac{\frac{1}{x-a}f(a)-\frac{1}{x-b}f(b)}{-\frac{b-a}{(x-a)(x-b)}},$
(2.2)

as a rational function with both the numerator and the denominator having
poles at the boundaries $a$ and $b$.

Consider next linear interpolation over triangles
$(\mathbf{p}_{0},\mathbf{p}_{1},\mathbf{p}_{2})\subset\mathbb{R}^{2}$ in the
plane. The usual formula for barycentric interpolation gives

$\displaystyle
f(\mathbf{x})=\frac{A_{0}f(\mathbf{p}_{0})+A_{1}f(\mathbf{p}_{1})+A_{2}f(\mathbf{p}_{2})}{A},$
(2.3)

which can be reorganized into the equivalent form

$\displaystyle
f(\mathbf{x})=\frac{\frac{1}{A_{1}A_{2}}f(\mathbf{p}_{0})+\frac{1}{A_{2}A_{0}}f(\mathbf{p}_{1})+\frac{1}{A_{0}A_{1}}f(\mathbf{p}_{2})}{\frac{A}{A_{0}A_{1}A_{2}}},$
(2.4)

with the notations shown in Figure 1.

Figure 1: Notations for barycentric coordinates. Figure 2: Canonical rational
function of a triangle.

Wachspress proposed generalized barycentric coordinates over convex polytopes
[17]. For a planar $n$-gon with vertices
$\mathbf{p}_{0},\ldots\mathbf{p}_{n-1}$ these coordinates are defined as:

$\displaystyle
f(\mathbf{x})=\sum_{i=0}^{n}\frac{\frac{C_{i}}{A_{i-1,i}A_{i,i+1}}}{\frac{\sum_{k}C_{k}A_{k-3,k-2}\cdots
A_{k+1,k+2}}{\prod_{k}A_{k,k+1}}}f(\mathbf{p}_{i}),$ (2.5)

where the indices are cyclical modulo $n$ – see Figure 1.

Figure 3: Canonical rational function of a pentagon.

In each of these cases, some terms in the numerator and denominator approach
infinity along an interpolated subset, which is reminiscent of Shepard’s
method [8, 13]. The rational functions in the denominators are illustrated in
Figure 2 and Figure 3. The common pattern involves functions with poles along
the boundaries of some shape. Our goal is to make this idea rigorous using the
notion of a positive geometry.

## 3 Positive Geometries and Canonical Differential Forms

The central concept of our work is that of a positive geometry – a relatively
new concept originating from mathematical physics. In this chapter, we give an
informal overview, and refer to [1] for technical details. For the necessary
background in projective and algebraic geometry, see e.g. [12, 7].

### 3.1 Definition of Positive Geometries

Positive geometries were introduced as generalizations of shapes with a
recursive structure similar to polytopes, defined by some sort of “positivity”
criterion (e.g. the interior of polytopes, or totally positive matrices [5]).
The definition was motivated by recent developments in quantum physics, where
the solution of differential equations in Fourier space led to rational
functions with poles at the boundaries of certain regions [1].

######  Definition 1.

A positive geometry is a pair $(X,X_{\geq 0})$, where $X$ is a $d$-dimensional
complex projective algebraic variety, and $X_{\geq 0}$ is an oriented semi-
algebraic subset of its real part, with a unique differential $d$-form
$\Omega(X,X_{\geq 0})$ called its canonical form, defined by recursion on the
boundary dimension:

  * •

If $d=0$, then $X$ is an (oriented) point, and $\Omega(X,X_{\geq 0})=\pm 1$
depending on the orientation.

  * •

If $d>0$, then the boundary components of $X_{\geq 0}$ are themselves positive
geometries, and the multivariate residue (see [1, A.3] or [7, Ch. 5]) along a
component is the canonical form for the associated positive geometry.

We stress that a positive geometry is determined by an ambient complex
manifold (most often a projective space $\mathbb{P}^{n}$), together with a
“positive” real subset, thus many different positive geometries could be
associated to the same ambient space.

For positive geometries over projective spaces with homogeneous coordinates
$\mathbf{x}=\left[x_{0}:x_{1}:\ldots x_{d}\right]$, the canonical form can
always be written in terms of a rational function [1, C.1]:

$\displaystyle\Omega(X,X_{\geq 0})=C(\mathbf{x})\omega(\mathbf{x}),$ (3.6)

where $C$ is called the canonical rational function of the positive geometry
and

$\displaystyle\omega(\mathbf{x})=\frac{1}{d!}x_{0}dx_{1}\wedge\ldots\wedge
dx_{d}+\ldots+(-1)^{d}x_{d}dx_{0}\wedge\ldots\wedge dx_{d-1}$

is the _standard measure_ on projective $d$-space.

### 3.2 Examples of Positive Geometries

Some elementary examples of positive geometries are the following:

  * •

Segments, bounded by two points $\mathbf{a}=\left[a:1\right]$ and
$\mathbf{b}=\left[b:1\right]$ in the projective line $\mathbb{P}^{1}$
parameterized using homogeneous coordinates. The canonical form at the point
$\mathbf{x}=\left[x:y\right]$ is

$\displaystyle\Omega(\mathbb{P}^{1},\left[a,b\right])=\frac{\left\langle\mathbf{b},\mathbf{a}\right\rangle}{\left\langle\mathbf{x},\mathbf{a}\right\rangle\left\langle\mathbf{x},\mathbf{b}\right\rangle}\omega(\mathbf{x}),$
(3.7)

where
$\left\langle\mathbf{v},\mathbf{w}\right\rangle:=\det(\mathbf{v},\mathbf{w})$
denotes the determinant of vectors of homogeneous coordinates.

  * •

Simplices in projective spaces. For triangles formed by three points
$\mathbf{p}_{i}=\left[x_{i}:y_{i}:1\right],i=0,1,2$ in the projective plane
$\Delta\subset\mathbb{P}^{2}$ parameterized using homogeneous coordinates
$\mathbf{x}=\left[x:y:z\right]$, the canonical form is

$\displaystyle\Omega(\mathbb{P}^{2},\Delta)$
$\displaystyle=\frac{1}{2}\frac{\left\langle\mathbf{p}_{0},\mathbf{p}_{1},\mathbf{p}_{2}\right\rangle^{2}}{\left\langle\mathbf{x},\mathbf{p}_{0},\mathbf{p}_{1}\right\rangle\left\langle\mathbf{x},\mathbf{p}_{1},\mathbf{p}_{2}\right\rangle\left\langle\mathbf{x},\mathbf{p}_{2},\mathbf{p}_{0}\right\rangle}\omega(\mathbf{x}).$
(3.8)

Both of these forms are invariant under independent scaling of the homogeneous
coordinates of the vertices, as well as the point of evaluation, and are thus
well-defined functions over projective spaces.

Many other examples of positive geometries were identified [1, Ch. 5]:

  * •

Planar regions bounded by a conic section and a line.

  * •

Regions in projective 3-space bounded by a quadric or cubic surface and a
plane.

  * •

Positive, real parts of _Grassmannians_ (manifolds of $k$-planes in
$n$-dimensional space, denoted $G(k,n)$).

  * •

Positive, real parts of _toric varieties_ [15].

These examples – called generalized simplices – all have canonical forms with
constant numerators.

The canonical forms of positive geometries are additive, i.e. the canonical
form of a union is the sum of the canonical forms of its parts. The poles
along boundaries meeting with opposite orientation will cancel, so that only
poles on the exterior boundary remain (technically, this is true for a “signed
triangulation of the empty set” – see [1, Ch. 3]). This implies that the
canonical forms of more complicated regions can be determined by
“triangulating” them. It follows that _convex polytopes_ – which can be
triangulated in the usual sense – are also positive geometries.

In analogy with generalized simplices, there are also various generalized
polytopes:

  * •

Convex regions of the projective plane bounded by straight lines and conics,
which are examples of _polycons_ , as defined by Wachspress [17].

  * •

_Grassmann polytopes_ , in particular _Amplituhedra_ , which are
generalizations of cyclic polytopes into Grassmannians.

Generalized polytopes have canonical forms with a non-constant numerator. In
fact, for polytopes and polycons the numerator is known as the _adjoint
polynomial_ [10, 2].

### 3.3 Relation to dual polytopes

A canonical form often has a natural geometric interpretation. In particular,
the canonical rational function of a convex projective polytope
$P\subset\mathbb{P}^{d}$ is the signed volume of its _polar dual_
$P_{\mathbf{x}}^{\ast}\subset(\mathbb{P}^{d})^{\ast}$, as shown in [1, Ch.
7.4.1]. The polar dual is the intersection of the dual projective cone of the
polytope, with the dual hyperplane of the point $\mathbf{x}\in P$, and its
volume is a rational function over $P$ computed by the integral formula

$\displaystyle\mathrm{Vol}(P_{\mathbf{x}}^{\ast})=\frac{1}{d!}\int_{\mathbf{y}\in
P_{\mathbf{x}^{\ast}}}\frac{1}{(\mathbf{x}^{T}\mathbf{y})^{d+1}}\omega(\mathbf{y}).$
(3.9)

## 4 Barycentric Interpolation over Positive Geometries

We claim that the canonical forms of positive geometries can be used to define
barycentric interpolation in a way similar to Shepard’s method.

Consider barycentric (linear) interpolation over a _segment_. Define the
weight function for the endpoint $a$ as the ratio of canonical forms for
positive geometries over the projective line

$\displaystyle\lambda_{a}(x)=\frac{\Omega(\mathbb{P}^{1},\left[a,x^{\ast}\right])}{\Omega(\mathbb{P}^{1},\left[a,b\right])},$
(4.10)

where $x^{\ast}$ is the _projective dual_ of the point $x$. If we choose
coordinates so that $x$ is the origin and $x^{\ast}$ is the point at infinity,
we get the barycentric formula (2.2) for linear interpolation.

The same construction applies to a _triangle_ as well. For the the vertex
$\mathbf{p}_{i}$, we take the ratio of two canonical forms over the projective
plane – that of the original triangle, and the triangle bounded by the two
sides meeting at $\mathbf{p}_{i}$ together with the dual line of the current
point $\mathbf{x}$. Using the notations of Figure 4:

$\displaystyle\lambda_{i}^{\Delta}(\mathbf{x})=\frac{\Omega(\mathbb{P}^{2},\Delta(l_{ki},l_{ij},\mathbf{x}^{\ast}))}{\Omega(\mathbb{P}^{2},\Delta(l_{ij},l_{jk},l_{ki}))}.$
(4.11)

This is simply the usual formula (2.4) for barycentric interpolation. Along
each of the sides, the forms (technically, their residues) restrict to linear
interpolation over a segment, as expected.

Figure 4: Triangles used for barycentric coordinates.

For a _convex polytope_ $P\subset\mathbb{P}^{2}$ we follow the same recipe –
the denominator for the vertex $\mathbf{p}_{i}$ will be the canonical form of
$P$, while the numerator is the canonical form defined by the sides meeting at
the vertex, with the dual line of the current point:

$\displaystyle\lambda_{i}^{P}(\mathbf{x})=\frac{\Omega(\mathbb{P}^{2},\Delta(l_{\left(i-1\right)i},l_{i\left(i+1\right)},\mathbf{x}^{\ast}))}{\Omega(\mathbb{P}^{2},P)}.$
(4.12)

These weight functions are the Wachpress coordinates (2.5) over $P$. The
generalization to higher-dimensional simplices and (simplicial) polytopes is
straightforward.

In each case, the numerators are defined by positive geometries that form a
signed triangulation of the domain. The additivity of canonical forms under
unions then implies that their sum is the canonical form of the original
polytope, and thus these functions form a _partition of unity_.

While these triangulations are not the most natural with respect to the
original polytope, they correspond to a natural triangulation of the polar
dual polytope including the origin (i.e. the current point $\mathbf{x}$).
Recalling the interpretation of canonical forms as dual volumes, the numerator
is seen as the volume of the dual pyramid formed by the current point and the
dual face of the vertex. Thus, we connect to the earlier work of [9], who
characterized Wachspress coordinates as ratios of polar dual volumes. Note
that a triangulation of the polar dual through its vertices is analogous to
Warren’s triangulation-based definition of the adjoint polynomial for a
polytope [18].

Wachspress coordinates can be generalized also to regions bounded by subsets
bounded by higher-order algebraic varieties, such as _polycons_ [17]. We omit
the discussion of these cases to conform to spatial limitations.

## 5 Discussion and Future Work

Our approach to barycentric interpolation with canonical forms of positive
geometries unifies earlier approaches using adjoint polynomials, dual volumes
and Shepard-like interpolation. An advantage of this framework is that it
extends to positive geometries other than polytopes, such as Grassmannians and
toric varieties.

We also mention that the definition of a positive geometry embeds the domain
into a higher-dimensional complex manifold, thus our approach can be viewed as
a multivariate generalization of complex analytical methods (contour
integrals, residues) used in univariate approximation theory [16].

### 5.1 Open Problem: Interpolation in Grassmannians

As was mentioned previously, certain “positive” subsets of Grassmannians are
also examples of positive geometries. Points in a Grassmannian $G(k,n)$ can be
represented by $k\times n$ matrices, and the positive geometry known as the
_positive Grassmannian_ corresponds to _totally positive_ matrices, which are
of great interest for approximation theory and geometric modeling [5].

The Grassmannian of 2-planes in 4-space, $G(2,4)$ – which is also the manifold
of lines within 3-space – is particularly interesting for many applications
[12]. $G(2,4)$ is a 4-dimensional hypersurface in $\mathbb{P}^{5}$ cut out by
a quadratic equation in Plücker coordinates, and the positive Grassmannian is
a semi-algebraic subset with non-linear boundaries. The line-geometric
analogue of a simplex might be related to the _tetrahedral line complex_ , the
boundary of which is the set of lines defined by the edges of a tetrahedron.
The combinatorial structure of this boundary is that of an octahedron – an
example of a _hypersimplex_ – as shown in Figure 5, where each vertex
represents a line along an edge of the tetrahedron, while each face represents
lines through either a vertex or a face [6].

Figure 5: Tetrahedral line complex and corresponding hypersimplex. Shaded
faces correspond to lines through vertices.

Being a positive geometry, the positive Grassmannian has a canonical form,
i.e. a rational function of Plücker coordinates with poles along its
boundaries [1, Ch. 5.5]. This suggests that generalizations of barycentric
coordinates into line space might be possible using our framework.

### 5.2 Open Problem: Generalized Positive Geometries for Mean-Value
Coordinates

Canonical forms are defined by rational functions, so Mean-Value Coordinates
(MVCs) [4] – defined by transcendental functions – are apparently incompatible
with the proposed framework. We could adapt the approach of [14], where MVCs
are expressed as dual Shepard interpolants, after deforming the original
boundary to a unit circle around the current point. A disc is not a positive
geometry in the usual sense – it lacks zero-dimensional boundary components,
for example. Nevertheless, we can easily find a projectively well-defined
function with singularities along a projective conic $\mathcal{C}$ given by
the quadratic equation $\mathbf{x}^{T}\mathbf{Q}\mathbf{x}=0$ (see [1, Ch. 10]
for a lengthy discussion):

$\displaystyle\Omega(\mathbb{P}^{2},\mathcal{C})=\frac{\pi\det(\mathbf{Q})^{\frac{3}{4}}}{(\mathbf{x}^{T}\mathbf{Q}\mathbf{x})^{\frac{3}{2}}}\omega(\mathbf{x}).$
(5.13)

Observe the similarity with the transfinite form of MVCs [4, Ch. 10], when
$\mathcal{C}$ is a circle. This kind of canonical function is not rational and
its singularities along $\mathcal{C}$ are not simple poles, but _branch
points_ (similar to the origin of the complex plane for fractional powers and
logarithms). The authors of [1] also identified such transcendental
generalizations of positive geometries as promising subjects for future
research.

### 5.3 Open Problem: Relation to Splines and Integral Geometry

Formulas such as the dual volume (3.9) also appear in the context of
multivariate (box/simplex/cone) splines [3], as Laplace transforms of
indicator functions. This suggests that splines and barycentric interpolants
could both fit within an even more general theoretical framework related to
integral geometry.

## Acknowledgements

This project has been supported by the Hungarian Scientific Research Fund
(OTKA, No.124727). The author thanks Tamás Várady for support and Péter Salvi
for interesting discussions.

## References

  * [1] N. Arkani-Hamed, Y. Bai, and T. Lam.  Positive geometries and canonical forms.  Journal of High Energy Physics, 2017(11):39, 2017.
  * [2] G. Dasgupta and E. Wachspress.  The adjoint for an algebraic finite element.  Computers & Mathematics with Applications, 55(9):1988–1997, 2008\.
  * [3] C. De Concini and C. Procesi.  Topics in Hyperplane Arrangements, Polytopes and Box-Splines.  Springer, 2010.
  * [4] M.S. Floater.  Generalized barycentric coordinates and applications.  Acta Numerica, 24:161–214, 2015.
  * [5] M. Gasca and C.A. Micchelli, editors.  Total Positivity and Its Applications.  Kluwer, 1996.
  * [6] I.M. Gelfand and R.D. MacPherson.  Geometry in Grassmannians and a generalization of the dilogarithm.  Advances in mathematics, 44(3):279–312, 1982.
  * [7] P. Griffiths and J. Harris.  Principles of Algebraic Geometry.  John Wiley & Sons, 1978.
  * [8] K. Hormann.  Barycentric interpolation.  In Approximation Theory XIV: San Antonio 2013. Springer, 2014.
  * [9] T. Ju, S. Schaefer, J. Warren, and M. Desbrun.  A geometric construction of coordinates for convex polyhedra using polar duals.  In Proceedings of the 3rd Eurographics Symposium on Geometry Processing. Eurographics, 2005.
  * [10] K. Kohn and K. Ranestad.  Projective geometry of Wachspress coordinates.  arXiv preprint arXiv:1904.02123, 2019.
  * [11] M. Meyer, A. Barr, H. Lee, and M. Desbrun.  Generalized barycentric coordinates on irregular polygons.  Journal of graphics tools, 7(1):13–22, 2002.
  * [12] H. Pottmann and J. Wallner.  Computational Line Geometry.  Mathematics and Visualization. Springer, 2001.
  * [13] V.L. Rvachev, T.I. Sheiko, V. Shapiro, and I. Tsukanov.  Transfinite interpolation over implicitly defined sets.  Computer Aided Geometric Design, 18(3):195–220, 2001.
  * [14] S. Schaefer, T. Ju, and J. Warren.  A unified, integral construction for coordinates over closed curves.  Computer Aided Geometric Design, 24(8-9):481–493, 2007.
  * [15] F. Sottile.  Toric ideals, real toric varieties, and the algebraic moment map.  In Topics in Algebraic Geometry and Geometric Modeling. AMS, 2003\.
  * [16] L.N. Trefethen.  Approximation Theory and Approximation Practice.  SIAM, 2013.
  * [17] E. Wachspress.  Rational Bases and Generalized Barycentrics: Applications to Finite Elements and Graphics.  Springer, 2016.
  * [18] J. Warren.  Barycentric coordinates for convex polytopes.  Advances in Computational Mathematics, 6(1):97–108, 1996.


Minimizing Pentagons in the Plane through Automated Reasoning]Minimizing Pentagons in the Plane
through Automated Reasoning

Bernardo Subercaseaux, John Mackey,
Marijn J. H. Heule, and Ruben Martins

Carnegie Mellon University, Pittsburgh, PA 15213, USA
{bsuberca, jmackey, mheule<EMAIL_ADDRESS>
We study $\mu_5(n)$, the minimum number of convex pentagons induced by $n$ points in the plane in general position. Despite a significant body of research in understanding $\mu_4(n)$, the variant concerning convex quadrilaterals, not much is known about $\mu_5(n)$. We present two explicit constructions, inspired by point placements obtained through a combination of Stochastic Local Search and a program for realizability of point sets, that provide $\mu_5(n) \leq \binom{\lfloor n/2 \rfloor}{5} + \binom{\lceil n/2 \rceil}{5}$.

Furthermore, we conjecture this bound to be optimal, and provide partial evidence by leveraging a MaxSAT encoding that allows us to verify our conjecture for $n \leq 16$.

§ INTRODUCTION

Ramsey theory, dating back to 1928, revolves around the question “How big must some structure be to guarantee that a particular property holds?” [22, 31]. In 1933, unaware of Ramsey's recent findings, Klein gave this question a geometric flavor by presenting the following problem [23]: If five points lie on a plane so that no three points form a straight line, prove that four of the points will form a convex quadrilateral. Klein's problem inspired two natural generalizations with a long lasting impact on combinatorial geometry:

For a given $k \geq 3$, is there always a minimum number of points  $n = g(k)$, such that any set of $n$ points in the plane, without three in a line, is guaranteed to contain $k$ points that are vertices of a convex $k$-gon?

For a given $k \geq 3$, what is the minimum number of convex $k$-gons, $\mu_k(n)$, that one can obtain by placing $n$ points in the plane without three in a line?

In that very year, 1933, Erdős and Szekeres rediscovered Ramsey theory in order to attack Problem <ref> [23], and published an affirmative answer in 1935, with a celebrated theorem establishing that $g(k) \leq \binom{2k - 4}{k-2} + 1$ [16].
Furthermore, in the same publication they conjectured that $g(k) = 2^{k-2} + 1$, which remains a tantalizing open problem for $k > 6$, despite significant progress [29]. Shortly after the 1935 publication, Szekeres and Klein married, leading Erdős to refer to Problem <ref> as the “Happy Ending Problem” [29].

Problem <ref>, on the other hand, is directly mentioned for the first time by Erdős and Guy in 1973 [15]:
“More generally, one can ask for the least number of convex $k$-gons determined by $n$ points
in the plane. As before, the ratio of this number to $\binom{n}{k}$ tends to a
positive limit as $n$ tends to infinity with $k$ fixed.” In other words, a corollary of the affirmative answer to Problem <ref> is that the limits

\[
c_k := \lim_{n \to \infty} \frac{\mu_k(n)}{\binom{n}{k}}
\]

are well defined and positive.
Nevertheless, determining the values $0 < c_k < 1$ has proven to be a challenging task in combinatorial geometry.
The case of $k=3$ leads immediately to $c_3 = 1$ as every set of $3$ points in general position forms a (convex) triangle.  Perhaps surprisingly, $c_4$[Also known as the rectilinar crossing constant due to the equivalence between minimizing convex quadrilaterals and minimizing the number of edge-crossings in rectilinear drawings of the $K_n$ graph [1].] is still unknown despite having received significant attention [4, 1], and the state-of-the-art bounds are:
\(
0.379972 \leq c_4 \leq 0.3804491869
\) [4, 5].

Computation has played a crucial role in improving the bounds on $c_4$, computing $\mu_k(n)$ for small values of $k$ and $n$, and in general, classifying small sets of points according to their geometric relationships [3]. Furthermore, these goals are tightly connected, as it is known that determining $\mu_k(n)$ (or having good bounds on it) for larger values of $n$ allows for better estimates of $c_k$ [1]. As of today, the value of $\mu_4(n)$ is only known for $n \leq 27$ and $n=30$ [1].
Much less is known for $k \geq 5$ [3, 7, 2], where the question raised by Erdős and Guy, 50 years ago, remains widely open. In this context, our work adds to the success of automated reasoning techniques for Erdős-Szekeres type problems [34, 33], providing new insight into $\mu_5(n)$ and $c_5$, and opening directions for studying $\mu_k(n)$ and $c_k$ for larger values of $k$ as well.

Improvements on $\mu_5(n)$. Brackets indicate the range of values in which $\mu_5(\cdot)$ was known to belong.

# of points $(n)$     $\prescript{\leq}{}{8}$     $9$     $10$     $11$     $12$     $13$     $14$     $15$     $16$
Previously [2]     0     1     2     7     [12, 13]
[20, 34]     [40, 62]     [60, 113]     —

Our work     0     1     2     7     12     27     42     77     112

Our contributions. This article makes progress on Problem <ref> in the particular case of $k=5$.
As shown in <Ref>, we fully determine $\mu_5(n)$ for $n \leq 16$, furthering prior results which reached $n = 11$ [2]. We start by providing some background into the geometry of the problem and known values of $\mu_5(n)$ in <Ref>, and continue in <Ref> by presenting an initial exploration of $\mu_5(n)$ through Stochastic Local Search (SLS) using signotopes.
Given the absence of open-source programs that find concrete point
realizations of signotopes, we present in <Ref> a simple local-search
program that finds them. We depict particular realizations obtained for the satisfying assignments that we found through SLS, which provide geometric insight into the problem. Based on said realizations, in <Ref> we propose and study two simple constructions providing a common upper bound of

\[
\mu_5(n) \leq \binom{\lfloor n/2\rfloor}{5} + \binom{\lceil n/2\rceil}{5},
\]

which we conjecture to be optimal.
<Ref> discusses the verification of the conjecture for $n \leq 16$ through MaxSAT, and finally, <Ref> discusses the impact of the newly found values of $\mu_5(n)$ for bounding $c_5$ and offers open questions and directions for future work.

§ BACKGROUND

§ ENCODING AND STOCHASTIC LOCAL SEARCH

§ REALIZABILITY

§ CONSTRUCTIONS

§ MAXSAT VERIFICATION

§ CONCLUDING REMARKS AND FUTURE WORK

§ ACKNOWLEDGEMENTS

This work is partially supported by the U.S. National Science Foundation (NSF) under grant CCF-2015545.

[1]
Bernardo M. Ábrego, Silvia Fernández-Merchant, and Gelasio Salazar,
The rectilinear crossing number of $k_n$ : Closing in (or are we?),
Thirty Essays on Geometric Graph Theory (New York, NY) (János Pach, ed.),
Springer New York, 2013, pp. 5–18 (en).

[2]
Oswin Aichholzer, [empty][colored] $k$-gons - Recent results on some
Erdős-Szekeres type problems, Proc. EGC2009 (2009), 43–52 (en).

[3]
Oswin Aichholzer, Franz Aurenhammer, and Hannes Krasser, Enumerating
order types for small sets with applications, Proceedings of the seventeenth
annual symposium on Computational geometry (New York, NY, USA), SCG ’01,
Association for Computing Machinery, June 2001, p. 11–18.

[4]
Oswin Aichholzer, Frank Duque, Ruy Fabila-Monroy, Oscar E. García-Quintero,
and Carlos Hidalgo-Toscano, An ongoing project to improve the
rectilinear and the pseudolinear crossing constants, Journal of Graph
Algorithms and Applications 24 (2020), no. 3, 421–432 (en).

[5]
Oswin Aichholzer, Frank Duque, Ruy Fabila-Monroy, Carlos Hidalgo-Toscano, and
Oscar E. García-Quintero, An ongoing project to improve the
rectilinear and the pseudolinear crossing constants, July 2019.

[6]
Oswin Aichholzer, Ruy Fabila-Monroy, Hernán González-Aguilar, Thomas Hackl,
Marco A. Heredia, Clemens Huemer, Jorge Urrutia, Pavel Valtr, and Birgit
Vogtenhuber, On k-gons and k-holes in point sets, Computational
Geometry 48 (2015), no. 7, 528–537.

[7]
Oswin Aichholzer, Thomas Hackl, and Birgit Vogtenhuber, On 5-gons and
5-holes, Lecture Notes in Computer Science, p. 1–13, Springer, Berlin,
Heidelberg, 2012 (en).

[8]
Florent Avellaneda, Evalmaxsat 2023, MaxSAT Evaluation 2023 (2023), 12.

[9]
Fahiem Bacchus, Matti Järvisalo, and Ruben Martins, Maximum
satisfiabiliy, Handbook of Satisfiability - Second Edition (Armin Biere,
Marijn Heule, Hans van Maaren, and Toby Walsh, eds.), Frontiers in Artificial
Intelligence and Applications, vol. 336, IOS Press, 2021, pp. 929–991.

[10]
Jeremias Berg, Bart Bogaerts, Jakob Nordström, Andy Oertel, and Dieter
Vandesande, Certified core-guided maxsat solving, International
Conference on Automated Deduction, Springer, 2023, pp. 1–22.

[11]
Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and
Gunter M. Ziegler, Oriented matroids, 2 ed., Encyclopedia of
Mathematics and its Applications, Cambridge University Press, Cambridge,

[12]
Alex Brodsky, Stephane Durocher, and Ellen Gethner, The rectilinear
crossing number of $k_{10}$ is $62$, The Electronic Journal of Combinatorics
(2001), R23–R23 (en).

[13]
Jessica Davies and Fahiem Bacchus, Postponing optimization to speed up
MAXSAT solving, Principles and Practice of Constraint Programming - 19th
International Conference, CP 2013, Uppsala, Sweden, September 16-20, 2013.
Proceedings (Christian Schulte, ed.), Lecture Notes in Computer Science, vol.
8124, Springer, 2013, pp. 247–262.

[14]
Jo Devriendt, Bart Bogaerts, Maurice Bruynooghe, and Marc Denecker,
Improved static symmetry breaking for SAT, Theory and Applications
of Satisfiability Testing - SAT 2016 - 19th International Conference (Nadia
Creignou and Daniel Le Berre, eds.), Lecture Notes in Computer Science, vol.
9710, Springer, 2016, pp. 104–122.

[15]
P. Erdős and R. K. Guy, Crossing number problems, The American
Mathematical Monthly 80 (1973), no. 1, 52–58.

[16]
P. Erdős and G. Szeckeres, A combinatorial problem in geometry,
p. 49–56, Birkhäuser Boston, Boston, MA, 2009 (en).

[17]
Stefan Felsner and Helmut Weil, Sweeps, arrangements and signotopes,
Discrete Applied Mathematics 109 (2001), no. 1, 67–94.

[18]
Alfredo García, Marc Noy, and Javier Tejel, Lower bounds on the number
of crossing-free subgraphs of $K_n$, Computational Geometry 16
(2000), no. 4, 211–221.

[19]
Frédéric Gardi, Thierry Benoist, Julien Darlay, Bertrand Estellon,
and Romain Megel, Mathematical programming solver based on local
search, Wiley, June 2014.

[20]
Stephan Gocht, Ruben Martins, Jakob Nordström, and Andy Oertel,
Certified CNF translations for pseudo-boolean solving, 25th
International Conference on Theory and Applications of Satisfiability
Testing, SAT 2022 (Kuldeep S. Meel and Ofer Strichman, eds.), LIPIcs, vol.
236, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022,
pp. 16:1–16:25.

[21]
Stephan Gocht and Jakob Nordström, Certifying parity reasoning
efficiently using pseudo-Boolean proofs, Proceedings of the 35th AAAI
Conference on Artificial Intelligence (AAAI '21), February 2021,
pp. 3768–3777.

[22]
Ron Graham and Steve Butler, Rudiments of ramsey theory, 2 ed., CBMS
regional conference series in mathematics, American Mathematical Society,
Providence, RI, November 2015.

[23]
Ronald L. Graham and Joel H. Spencer, Ramsey theory, Scientific American
263 (1990), no. 1, 112–117.

[24]
Marijn J. H. Heule, Oliver Kullmann, and Armin Biere, Cube-and-conquer
for satisfiability, Handbook of Parallel Constraint Reasoning (Youssef
Hamadi and Lakhdar Sais, eds.), Springer, 2018, pp. 31–59.

[25]
Abdelraouf Ishtaiwi, John Thornton, Abdul Sattar, and Duc Nghia Pham,
Neighbourhood clause weight redistribution in local search for sat,
Principles and Practice of Constraint Programming - CP 2005 (Peter van Beek,
ed.), Springer, 2005, pp. 772–776.

[26]
Donald E. Knuth, Axioms and hulls, Lecture Notes in Computer Science,
p. 1–98, Springer, Berlin, Heidelberg, 1992 (en).

[27]
Chu-Min Li, Zhenxing Xu, Jordi Coll, Felip Manyà, Djamal Habet, and Kun
He, Combining clause learning and branch and bound for maxsat, 27th
International Conference on Principles and Practice of Constraint Programming
(Laurent D. Michel, ed.), LIPIcs, vol. 210, Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2021, pp. 38:1–38:18.

[28]
Hakan Metin, Souheib Baarir, Maximilien Colange, and Fabrice Kordon,
Cdclsym: Introducing effective symmetry breaking in SAT solving,
Tools and Algorithms for the Construction and Analysis of Systems - 24th
International Conference, TACAS 2018, Held as Part of ETAPS, Proceedings,
Part I (Dirk Beyer and Marieke Huisman, eds.), Lecture Notes in Computer
Science, vol. 10805, Springer, 2018, pp. 99–114.

[29]
W. Morris and V. Soltan, The Erdős-Szekeres problem on points
in convex position – a survey, Bulletin of the American Mathematical
Society 37 (2000), no. 4, 437–458 (en).

[30]
Tobias Paxian, Sven Reimer, and Bernd Becker, Pacose: An iterative
sat-based maxsat solver, MaxSAT Evaluation 2018 (2018), 20.

[31]
F. P. Ramsey, On a problem of formal logic, Proceedings of the London
Mathematical Society s2-30 (1930), no. 1, 264–286.

[32]
Edward R. Scheinerman and Herbert S. Wilf, The rectilinear crossing
number of a complete graph and Sylvester’s “four point problem” of
geometric probability, The American Mathematical Monthly 101
(1994), no. 10, 939–943.

[33]
Manfred Scheucher, Two disjoint 5-holes in point sets, Computational
Geometry 91 (2020).

[34]
, A sat attack on Erdős-Szekeres numbers in $r^d$ and the
empty hexagon theorem, Computing in Geometry and Topology 2 (2023),
no. 1, 2:1–2:13.

[35]
Peter W. Shor, Stretchability of pseudolines is NP-hard., Applied
Geometry And Discrete Mathematics, Proceedings of a DIMACS Workshop,
Providence, Rhode Island, USA, September 18, 1990 (Peter Gritzmann and Bernd
Sturmfels, eds.), DIMACS Series in Discrete Mathematics and Theoretical
Computer Science, vol. 4, DIMACS/AMS, 1990, pp. 531–554.

[36]
Aaron Stump, Geoff Sutcliffe, and Cesare Tinelli, Starexec: A
cross-community infrastructure for logic solving, Automated Reasoning - 7th
International Joint Conference, IJCAR 2014, Held as Part of the Vienna
Summer of Logic, VSL 2014 (Stéphane Demri, Deepak Kapur, and
Christoph Weidenbach, eds.), Lecture Notes in Computer Science, vol. 8562,
Springer, 2014, pp. 367–373.

[37]
Bernardo Subercaseaux and Marijn Heule, Toward optimal radio colorings of
hypercubes via sat-solving, Proceedings of 24th International Conference on
Logic for Programming, Artificial Intelligence and Reasoning (Ruzica Piskac
and Andrei Voronkov, eds.), EPiC Series in Computing, vol. 94, EasyChair,
2023, pp. 386–404.

[38]
Bernardo Subercaseaux and Marijn J. H. Heule, The packing chromatic
number of the infinite square grid is 15, Tools and Algorithms for the
Construction and Analysis of Systems - 29th International Conference, TACAS
2023, Held as Part of ETAPS 2022, Proceedings, Part I (Sriram
Sankaranarayanan and Natasha Sharygina, eds.), Lecture Notes in Computer
Science, vol. 13993, Springer, 2023, p. 389–406.

[39]
George Szekeres and Lindsay Peters, Computer solution to the 17-point
Erdős-Szekeres problem, The ANZIAM Journal 48 (2006), no. 2,

[40]
Dave A. D. Tompkins and Holger H. Hoos, UBCSAT: An implementation and
experimentation environment for SLS algorithms for SAT and MAX-SAT,
Theory and Applications of Satisfiability Testing (Berlin, Heidelberg)
(Holger H. Hoos and David G. Mitchell, eds.), Springer, 2005, pp. 306–320.

[41]
Dieter Vandesande, Wolf De Wulf, and Bart Bogaerts, Qmaxsatpb: A
certified maxsat solver, International Conference on Logic Programming and
Nonmonotonic Reasoning, Springer, 2022, pp. 429–442.

[42]
Alex Wang, On quadratically constrained quadratic programs and their
semidefinite program relaxations, July 2022.