On Geodesic Disks Enclosing Many Points¹¹1Since the acceptance of this paper by the WADS Program Committee, the authors have improved some bounds that can be found in the full version [11].

Given a set $S$ of $n$ points in the plane in general position – no three of them are collinear and no four of them are cocircular – there always exist two points $u,v\in S$ such that any disk that contains $u$ and $v$ also contains a constant fraction of $S$. Neumann-Lara and Urrutia [19] proved that this constant fraction is at least $\lceil \frac{n-2}{60}\rceil$. This bound was improved in a series of papers [14, 15] culminating in the best known lower bound of about $\frac{n}{4.7}$ by Edelsbrunner et al. [13]. Hayward et al. [15] gave an upper bound by constructing a set of $n$ points such that for every pair of points $u,v$, there exists a disk with $u,v$ on its boundary containing less than $\lceil \frac{n}{4}\rceil$ points, thereby showing that $\lceil \frac{n}{4}\rceil +1$ is an upper bound for the problem. In addition, they studied the problem for point sets in convex position, giving a tight bound of $\lceil \frac{n}{3}\rceil +1$. Another version of the problem is to consider disks in the plane having the points $u$ and $v$ as diametral endpoints [2]. In this case, a tight bound of $\lceil \frac{n}{3}\rceil +1$ for both the convex and non-convex cases was shown.

The best known lower bound of $\left(\frac{1}{2}-\frac{1}{\sqrt{12}}\right)n+O(1)\approx \frac{n}{4.7}$ was obtained in multiple ways, see [12, 13, 23]. Edelsbrunner et al. [13] were the first to show this using techniques related to the order-$k$ Voronoi diagram. Ramos and Viaña [23] used known results about $j$-facets of point sets in ${ℝ}^3$. In fact, these results allowed Ramos and Viaña to prove that there is always a pair of points such that any disk through them has at least $\frac{n}{4.7}$ points both inside and outside the disk.

Generalizations of the original problem to higher dimensions have been studied by Bárány et al. [6] who proved that any set $S\subset {ℝ}^d$ of $n$ points in general position contains a subset $A$ of size $m=\lfloor \frac{1}{2}(d+3)\rfloor$ such that, any ball with $A$ on its boundary, contains at least $\frac{m!(d-m-1)!}{d!}n$ other points of $S$. Moreover, Bárány and Larman extended the results in [19] from Euclidean balls to ellipses in ${ℝ}^2$ and, more generally, to quadrics in ${ℝ}^d$ [5]. In particular, they showed that any set $S\subset {ℝ}^d$ of $n$ points contains a subset $A$, of size $\lfloor \frac{1}{4}d(d+3)\rfloor +1$, with the property that any quadric through $A$, contains at least $\frac{n}{s{2}^{s+1}}$ points of $S$, where $s=\frac{(d+1)(d+2)}{2}$.

A colored version of the problem has also been studied in the literature: Given a set $S$ of $\frac{n}{2}$ red and $\frac{n}{2}$ blue points in the plane, there always exists a bichromatic pair of points $u,v\in S$ such that any disk containing $u$ and $v$ contains at least a constant fraction of the $n$ points. Prodromou [22] proved²²2Using techniques from Edelsbrunner et al. [13], a PhD thesis written in Spanish and not published elsewhere had claimed before a lower bound of $\frac{23n}{250}\approx \frac{n}{11}$ [25]. that any set $S\subset {ℝ}^d$ colored with $k=\lfloor \frac{d+3}{2}\rfloor$ colors contains a subset $A\subset S$ of $k$ points, one of each color, such that any ball through all points in $A$ contains at least $\frac{|S|}{2k{3}^k}$ points of $S$, which gives a fraction $\frac{n}{36}$ for points in the plane. This fraction for the two-dimensional case was later improved in [12] to $\left(\frac{1}{2}-\frac{1}{\sqrt{8}}\right)n-o(n)\approx \frac{n}{6.8}$.

We note that all the upper bounds in the Euclidean setting translate directly to the geodesic setting by enclosing the constructions in a large enough triangle. Thus, in this paper, we focus mainly on the lower bounds and address all variants of the problem in the case where $S$ is a set of $n$ points inside a simple polygon $P$. In addition, throughout the paper, we consider that $n\ge 21$, so that all our results hold.

We summarize all our results and compare them with the Euclidean setting in Table 1. In Section 3, we present an overview of key properties of shortest paths in $P$ (which we refer to as the geodesic setting), emphasizing both their similarities to and differences from the Euclidean case. It is these differences that pose challenges we address to extend the results to the geodesic setting. Using these properties, in Section 4, we extend the lower bounds from the Euclidean case [14, 19] to the geodesic setting. While the upper bounds carry over directly, the lower bounds require new arguments due to the differences outlined in Section 3. For instance, unlike the Euclidean metric, which has bounded doubling dimension, the doubling dimension of the geodesic metric is not necessarily bounded since it depends on the number of reflex vertices of $P$. Additionally, we establish a tight bound for the case where the point set is in geodesically convex position. In Section 5, we show that the techniques in [2], where only diametral disks are considered, can be generalized to the geodesic setting. Finally, in Section 6 we extend the results in [22, 25] for two-colored points.

The problem of studying the largest number of points contained in any disk through two points inside a polygon is distinct from the planar case. As illustrated in Figure 1, a geodesic disk of radius $r$ in a polygon $P$ can be strictly contained in a Euclidean disk of radius $r$. As such, in this setting, it is unclear whether there always exists a pair of points such that any geodesic disk through them can contain the same number of points as in the Euclidean setting.

A sequence of points in the plane, $p_1,\mathrm{\dots },p_n$, forms a polygonal chain where the edges of the chain are the segments $p_i{p}_{i+1}$, for $i\in \{1,\mathrm{\dots },n-1\}$. A polygonal chain is simple if consecutive edges intersect at their common point and non-consecutive segments do not intersect. In a graph theoretic sense, this is a path. A simple polygon is a simple closed polygonal chain, i.e. a cycle. Informally, a polygon $P$ is a weakly-simple polygon provided that a slight perturbation of the vertices of the polygon results in a simple polygon. See Akitaya et al. [1] for a formal definition of weakly-simple as well as an algorithm to quickly recognize weakly-simple polygons. Given a pair of points $u,v$ in a polygon $P$, the geodesic (or shortest) path from $u$ to $v$ in $P$ is denoted by $g(u,v)$. It is well-known that $g(u,v)$ is a polygonal chain. The length of this path is the sum of the lengths of its edges and is denoted by $|g(u,v)|$.

A subset $P^{\prime }$ of $P$ is called geodesically convex if, for all pairs of points $u,v\in P^{\prime }$, the geodesic path $g(u,v)$ is contained in $P^{\prime }$. The geodesic convex hull of a set $S$ of points in $P$ is the geodesically convex set of minimum area that contains $S$. We say that $S$ is in geodesically convex position if every point of $S$ is on the boundary of the geodesic convex hull of $S$. A geodesic triangle on three points $a,b,c\in P$, denoted $\mathrm{△}(a,b,c)$, is a weakly-simple polygon whose boundary consists of $g(a,b)$, $g(b,c)$, and $g(c,a)$. The geodesic paths $g(a,b)$ and $g(a,c)$ follow a common route from $a$ until they diverge at a point $a^{\prime }$ (which may be $a$ itself). Similarly, let $b^{\prime }$ be the point where $g(b,a)$ and $g(b,c)$ diverge, and $c^{\prime }$ be the point where $g(c,a)$ and $g(c,b)$ diverge. The geodesic triangle $\mathrm{△}(a^{\prime },b^{\prime },c^{\prime })$ is a simple polygon that has $a^{\prime },b^{\prime }$ and $c^{\prime }$ as its convex vertices. The geodesic triangle $\mathrm{△}(a^{\prime },b^{\prime },c^{\prime })$ is referred to as the geodesic core of $\mathrm{△}(a,b,c)$ with the vertices $a^{\prime },b^{\prime },c^{\prime }$ referred to as the core vertices corresponding to the vertices $a,b,c$, respectively. The geodesic core of $\mathrm{△}(a,b,c)$ is denoted as $\mathrm{▽}(a,b,c)$ [9, 21]. In addition, $\mathrm{\angle }abc$ denotes the convex angle formed by the two edges of the geodesic core adjacent to the core vertex $b^{\prime }$ in $\mathrm{▽}(a,b,c)$. See Figure 2.

A geodesic disk centered at $c\in P$ with radius $r\ge 0$ is the set $D(c,r)=\{x\in P:|g(c,x)|\le r\}$. In the plane, there always exists a disk through three given points, assuming they are not collinear. When we refer to a disk through a set of points, we mean that the points are on the boundary of the disk. In a simple polygon, it is no longer true that there always exists a geodesic disk through three given points. This essentially means that given three points in a simple polygon, there does not always exists a point in the polygon that is geodesically equidistant to all three. However, if there is a geodesic disk through three points in a polygon, then it is unique [4]. Given two points $u$ and $v$, there always exists a geodesic disk through $u$ and $v$ centered at $c_{uv}$, the midpoint of $g(u,v)$, called the diametral geodesic disk.

A set $S^{\prime }$ of at least three points in $P$ is geodesically collinear if $\exists x,y\in S^{\prime }$ such that $S^{\prime }\subset g(x,y)$, see set $\{x,c,y\}$ in Figure 1. Similarly, a set $S^{\prime \prime }$ of at least four points is geodesically cocircular if there exists a geodesic disk with $S^{\prime \prime }$ on its boundary, see set $\{w,x,y,z\}$ in Figure 1. A set $S$ of $n$ points in a polygon $P$ is said to be in general position if no three points in $S$ are geodesically collinear and no four points in $S$ or the boundary of $P$ are geodesically cocircular. In this paper we only consider sets $S$ in general position in polygons $P$ with the extra condition that there are no two points $x,y\in S$ and a reflex vertex $p$ on the boundary of $P$ such that $y\subset g(x,p)$.

Given two points $u$ and $v$, the extension path $\mathrm{\ell }(u,v)$ is defined as follows: extend the first and last segment of $g(u,v)$ until they properly intersect with $P$. Denote these extension points on the boundary as $\widehat{u}$ and $\widehat{v}$, respectively. See the red path in Figure 2. Note that if $u$ (or $v$) is on the boundary of $P$ then $\widehat{u}=u$ (or $\widehat{v}=v$). Also note that, because of the extra condition added to the general position, the extensions cannot touch a reflex vertex $p$ on the boundary of the polygon $P$. The extension path $\mathrm{\ell }(u,v)$ naturally partitions the polygon into two weakly-simple polygons. We say that a point $w$ is to the left (resp., right) of $g(u,v)$ if $w$ belongs to the weakly-simple polygon to the left (resp., right) of $\mathrm{\ell }(u,v)$, when considering $\mathrm{\ell }(u,v)$ oriented from $u$ to $v$. In addition, we define the left (resp., right) half-polygon of the path $g(u,v)$ as the set of points that are to the left (resp., right) of its extension path $\mathrm{\ell }(u,v)$ and denote it as $P^{+}(u,v)$ (resp., $P^{-}(u,v)).$

Given two points $u,v\in S$, the bisector $b(u,v)$ is the set of all points that are equidistant to $u$ and $v$. In this paper, as in [3], we assume that no bisector $b(u,v)$ passes through a vertex of $P$. Hence, $b(u,v)$ is a continuous curve connecting two points on the boundary of $P$. Moreover, $b(u,v)$ can be decomposed into $O(|P|)$ pieces [3], each of which is a subarc of a hyperbola (that could degenerate to a line segment).

In this section we describe some of the similarities and differences concerning Euclidean and geodesic disks that arise when proving the main results in this paper.

In this section we provide a generalization to the geodesic setting of lower bounds that are known for the original problem in the plane. In particular, we generalize results from [14, 15, 19]. We note that upper bounds for the Euclidean setting are in general also valid for the geodesic setting, since one can take the constructions provided in [2, 12, 14], and enclose the relevant set of points in a bounding polygon, big enough so that the geodesic disks through every three points coincide with the corresponding Euclidean disks.

We begin by adapting some definitions and results from [19] to our setting. The intersection number $I(S)$ of a set of points $S$ in a polygon is defined as the number of different geodesic paths $g(u,v)$, $g(x,y)$ for $u,v,x,y\in S$ such that $g(u,v)\cap g(x,y)\ne \mathrm{\varnothing }$. Then, the intersection graph $G(S)=(V(G(S)),E(G(S)))$ is defined with $V(G(S))=\{g(u,v)|u,v\in S,u\ne v\}$, and two vertices $g(u,v)$, $g(x,y)$ being joined by an edge in $G(S)$ if $g(u,v)\cap g(x,y)\ne \mathrm{\varnothing }$. Finally, the oriented graph $\overrightarrow{G}(S)$ of $G(S)$ is defined orienting an edge $g(u,v)-g(x,y)$ as $g(u,v)\to g(x,y)$ if any geodesic disk through $u$ and $v$ contains $x$ or $y$, or otherwise orienting $g(x,y)\to g(u,v)$. This orientation is consistent because of Lemma 3.