On the Doubling Dimension and the Perimeter of Geodesically Convex Sets in Fat Polygons

In computational geometry, the standard way to model planar objects or regions is by polygons. Because polygons can have very complicated shapes and/or interact with each other in complicated ways, developing efficient solutions for algorithmic problems involving polygons is not always easy. In practice, however, the objects or regions under consideration are usually fairly well-behaved. The realistic input models paradigm [13] suggests to make this precise by defining properties of the input that are expected to be satisfied in practice and that allow for easier and/or more efficient algorithmic solutions.

One such property that has been studied extensively is fatness, where the underlying assumption is that real-world objects or regions are not extremely thin; see below for more precise definitions. For example, there have been results on motion-planning in environments where the obstacles are fat [26, 27] on various graphics-related problems involving fat objects [1, 21, 11, 10], on flow problems on terrains consisting of fat triangles [9], on various data-structure problems for fat objects [16, 20, 23], and more. Many of these results use one of the following two fundamental results: (i) the union complexity of $n$ constant-complexity fat polygons in the plane is near-linear; see [3] and the references therein; and (ii) any set of $n$ constant-complexity disjoint fat objects in the plane admits a hierarchical decomposition of the plane into constant-complexity cells that each intersect $O(1)$ objects [7]. Note that both results concern constant-complexity objects and that they essentially say something about the part of the space outside the objects. We are interested in what happens inside a fat polygon. In particular, we are interested in properties of the metric space $(P,{\mathrm{dist}}_{\mathrm{g}})$ where $P$ is a fat polygon (possibly with holes) and ${\mathrm{dist}}_{\mathrm{g}}$ is the geodesic distance. In other words, ${\mathrm{dist}}_{\mathrm{g}}(p,q)$ is the length of a shortest path between two points $p$ and $q$ in $P$. There has been work on guarding and triangulating fat polygons [2], but the special properties that the metric space $(P,{\mathrm{dist}}_{\mathrm{g}})$ may or may not have for fat polygons have not been studied much, to the best of our knowledge. This is surprising as problems involving shortest paths in polygons have received widespread attention, and fatness has been studied and used extensively as well. The only paper that is closely related to our work is by Bose, Cheong, and Dujmovic [5], who study the perimeter of fat objects, as discussed below.

The study of fat polygons was initiated by Matoušek et al. [22], who studied the union complexity of $\alpha$-fat triangles, which are triangles whose angles are at least $\alpha$, for some fixed constant $\alpha >0$. Since then, the concept of fatness has been generalized in different ways, both to convex and to non-convex objects. For convex objects, all definitions are equivalent in the sense that a convex object that is fat under one definition is also fat under the other definitions [25, 28]. Our interest lies in non-convex objects, since inside a convex object the geodesic distance is identical to the Euclidean distance. For non-convex objects, different fatness definitions have been proposed as well, but these are no longer equivalent. We discuss the most popular ones, focusing on definitions that apply to polygons.

Overmars, Halperin, and Van der Stappen [26] define a polygon $P$ to be $\gamma$-fat if, for any Euclidean disk $D$ centered inside $P$ and not fully containing $P$, we have $\mathrm{area}(P\cap D)⩾\gamma \cdot \mathrm{area}(D)$, for some fixed constant $\gamma >0$. This definition still allows the polygon to have very thin parts, as shown in Figure 1(i).

As a result, a collection of $n$ $\gamma$-fat, constant-complexity polygons can have quadratic union complexity. Hence, De Berg [8] introduced locally $\gamma$-fat polygons; here we require that for any Euclidean disk $D$ centered inside $P$ and not fully containing $P$, we have $\mathrm{area}(P\sqcap D)⩾\gamma \cdot \mathrm{area}(D)$, where $D\sqcap P$ denotes the connected component of $D\cap P$ that contains the center of $D$; see Figure 1(ii).

A third definition, by Efrat [15], is the following: a polygon is $(\alpha ,\beta )$-covered if for every $p$ on the boundary $\partial P$, there exists an $\alpha$-fat triangle $T_p\subset P$ with $p$ as a vertex such that each side of $T_p$ has length at least $\beta \cdot \mathrm{diam}(P)$, where $\alpha$ and $\beta$ are fixed positive constants. We will refer to such a triangle $T_p$ as a witness triangle for the point $p$; see Figure 1(i). This is a stronger condition than local fatness: any $(\alpha ,\beta )$-covered polygon is locally $\gamma$-fat for a constant $\gamma$ that depends only on the constants $\alpha$ and $\beta$, but the reverse is not true [8].

The three definitions above also apply to non-polygonal domains, even if they have holes.

Recall that a metric space $(𝒳,d)$ is $c$-doubling if every ball of radius $r$ in the space $𝒳$ can be covered by $c$ balls of radius $r/2$. The doubling dimension of the metric space is defined to be ${\log }_{2}c$. If $c$ is a constant, then we say that the metric space has bounded doubling dimension. Spaces of bounded doubling dimension generalize Euclidean space of constant dimension, and many problems can be solved (almost) as efficiently on spaces of bounded doubling dimension as they can in Euclidean space. Unfortunately, if $P$ is an arbitrary polygon then the metric space $(P,{\mathrm{dist}}_{\mathrm{g}})$ may not have bounded doubling dimension. The first problem we study is therefore: does the metric space $(P,{\mathrm{dist}}_{\mathrm{g}})$ necessarily have bounded doubling dimension when $P$ is fat?

For the fatness definition of Overmars et al. [26], the answer is easily seen to be no, as exemplified by the polygon in Figure 1(i): the ball centered at the red point in the middle of the polygon and whose radius $r$ is the geodesic distance to the top-right vertex, needs $\mathrm{\Omega }(n)$ geodesic balls of radius $r/2$ to be covered. Our first two results, presented in Section 2, concern the doubling dimension of locally-fat polygons and $(\alpha ,\beta )$-covered polygons.

• $\mathrm{■}$

  We show that locally-fat polygons do not necessarily have bounded doubling dimension. More precisely, we show that for any $n⩾3$ there exists a simple polygon $P$ with $n$ vertices and a geodesic disk $D$ in $P$ such that $\mathrm{\Omega }(n^{1/3})$ geodesic disks of radius $r$ are needed to cover $D$, where $r=\mathrm{radius}(D)$.

• $\mathrm{■}$

  On the positive side, we prove that the doubling dimension of any $(\alpha ,\beta )$-covered polygon is upper bounded by a constant that only depends on the constants $\alpha$ and $\beta$ and not on the number of vertices of the polygon. This result even holds for $(\alpha ,\beta )$-covered domains with curved boundaries and holes.

The fact that $(\alpha ,\beta )$-covered polygonal regions have bounded doubling dimension immediately implies a plethora of results that improve upon known results for non-fat polygons; we mention several of them at the end of Section 2.

After studying the doubling dimension of fat polygons, we turn our attention in Section 3 to the following problem: can the perimeter $\mathrm{per}(R)$ of a geodesically convex polygonal region $R$ be bounded in terms of its geodesic diameter ${\mathrm{diam}}_{\mathrm{g}}(R)$, or perhaps even in terms of its Euclidean diameter $\mathrm{diam}(R)$? For arbitrary polygons the answer is clearly no. In the polygon of Figure 1(i) the perimeter $\mathrm{per}(P)$ of $P$, which is geodesically convex, is $\mathrm{\Omega }(n\cdot {\mathrm{diam}}_{\mathrm{g}}(P))$, and hence arbitrarily larger than $\mathrm{diam}(P)$. Bose, Cheong, and Dujmović [5] showed that the same can happen for locally-fat polygons, via the Koch snowflake. For $(\alpha ,\beta )$-covered simple polygons, on the other hand, they showed that $\mathrm{per}(P)=O(\mathrm{diam}(P))$, where the constant of proportionality only depends on the constants $\alpha$ and $\beta$ and not on the number of vertices of the polygon. The applicability of this result is limited, because it only bounds the perimeter of the polygon itself and not of geodesically convex sets inside the polygon. We show that the result also holds in this much more general setting.

• $\mathrm{■}$

  For any geodesically convex polygonal set $R$ in an $(\alpha ,\beta )$-covered polygonal domain $P$, we have $\mathrm{per}(R)=O(\mathrm{diam}(R))$.

A fairly immediate consequence of this result is the existence of an $\epsilon$-coreset of size $O(1/\epsilon )$ for furthest-neighbor queries in an $(\alpha ,\beta )$-covered simple polygon $P$. This improves on the $O(1/{\epsilon }^2)$ bound recently proved by De Berg and Theocharous [12] for general simple polygons. The result can also be used to obtain an algorithm for the closest-pair problem on a set $S$ of $m$ points in $P$ whose expected running time is linear in $m$, as explained in Section 4.

We denote the Euclidean disk of radius $r$ centered at a point $p\in {ℝ}^2$ by $D(p,r)$ and we denote the Euclidean distance between two points $p,q$ by $|pq|$. For a polygon $P$, which will always be clear from the context, and two points $p,q\in P$, we use $\pi (p,q)$ to denote the shortest path between $p$ and $q$ inside $P$, and we denote the length of this path by $\Vert \pi (p,q)\Vert$. Thus, ${\mathrm{dist}}_{\mathrm{g}}(p,q)=\Vert \pi (p,q)\Vert$. The geodesic disk of radius $r$ centered at a point $p\in P$ is denoted by $D_{\mathrm{g}}(p,r)$. Recall that $\mathrm{diam}(P)$ denotes the Euclidean diameter of $P$ and that ${\mathrm{diam}}_{\mathrm{g}}(P)$ denotes the geodesic diameter. From now on, when we speak of the doubling dimension of $P$, we always refer to the doubling dimension of the metric space $(P,{\mathrm{dist}}_{\mathrm{g}})$.

Let $S$ be an axis-aligned square of side length $\mathrm{diam}(R)$ that contains $R$. We partition $S$ into a regular $g\times g$ grid $𝒢$, where $g:=\lceil \frac{2}{\beta \sin \alpha }\rceil$. Let $s:=\mathrm{diam}(R)/g$ be the side length of a grid cell. Then $s⩽\frac{\beta \sin \alpha }{2}\cdot \mathrm{diam}(R)$, and each cell $C\in 𝒢$ satisfies

Moreover,

We will need the following lemma.

It suffices to prove that the side $e$ of $T_p$ opposite to $p$ lies fully outside $C$. Assume for a contradiction that there exists a point $q\in e$ that is contained in $C$. Since $p\in C$ and $q\in C$, we have that $\mathrm{diam}(C)⩾|pq|$. Moreover, $|pq|⩾h_p$, where $h_p$ is the height of $T_p$ from $p$. Since $h_p⩾\sin \alpha \cdot \beta \cdot \mathrm{diam}(R)$, we have

which contradicts Inequality (1). $◀$ Let $𝒟=\{d_i:=i\frac{\alpha }{4}\mid i\in \mathbb{Z}\text{ and }0⩽i⩽\frac{8\pi }{\alpha }\}$ be a set of canonical directions.¹¹1With a slight abuse of terminology, we identify an angle $d_i\in 𝒟$ with the direction of a vector whose counterclockwise angle with the positive $x$-axis is $d_i$. For a point $p\in P$ and a direction $d$, let $\rho (p,d)$ be the ray starting from $p$ and going into the direction $d$. Let $C$ be a cell in $𝒢$ and consider a point $p\in \partial P\cap C$ that lies in the relative interior of an edge $e$ of $\partial P$. We say a direction $d_i\in 𝒟$ is good for $p$ if the following holds for the ray $\rho (p,d_i)$:

1. (i)

   $\rho (p,d_i)$ makes an angle of at least $\alpha /4$ with the edge $e$, and

2. (ii)

   $\rho (p,d_i)$ hits $\partial C$ before hitting $\partial P$.

The following lemma will allow us to bound $\Vert {\mathrm{\Gamma }}_1\Vert$.

For each $d_i\in 𝒟$, let $X_i\subseteq X$ be the set of points where $d_i$ is good. Note that $\Vert X\Vert ⩽{\sum }_{d_i\in 𝒟}\Vert X_i\Vert$.

Fix a direction $d_i$ and consider $X_i$. Assume wlog that $d_i$ is the vertically upward direction. We define a mapping $f_i:X_i\to \partial C$ such that $f_i(p)$ is the point where $\rho (p,d_i)$ hits $\partial C$; see Figure 7.

Observe that $f_i$ is injective. Indeed, if $q=f_i(p)$ then $p$ is the unique point in $X_i$ that is hit by a vertically downward ray from $q$. Let $\text{vd}(P)$ be the vertical decomposition of $P$, and consider a trapezoid $\mathrm{\Delta }\in \text{vd}(P)$. Let $X_i(\mathrm{\Delta })$ be the part of $X_i$ contained in the bottom side of $\mathrm{\Delta }$ – the top side cannot contain any part of $X_i$ – and assume that $X_i(\mathrm{\Delta })\ne \mathrm{\varnothing }$. Observe that $f_i(p)\in \mathrm{\Delta }\cap \partial C$ for all $p\in X_i(\mathrm{\Delta })$. Since the angle between $\rho (p,d_i)$ and the bottom side of $\mathrm{\Delta }$ is at least $\alpha /4$, we thus have $\Vert X_i(\mathrm{\Delta })\Vert ⩽\frac{1}{\sin (\alpha /4)}\cdot \Vert \partial C\cap \mathrm{\Delta }\Vert$. Hence,

Finally, we bound $\Vert X\Vert$ by summing over all canonical directions:

This proves the lemma. $◀$ We can now bound $\Vert \partial P\cap S\Vert$. Note that this immediately implies the same bound for $\Vert {\mathrm{\Gamma }}_1\Vert$, since ${\mathrm{\Gamma }}_1\subseteq \partial P\cap S$.

Fix a grid cell $C\in 𝒢$ and consider $X:=\partial P\cap C$. Let $p\in X$ be a point that lies in the relative interior of an edge $e$ of $\partial P$, and let $T_p$ be its witness triangle. Since the angle of $T_p$ at $p$ is at least $\alpha$, there are at least three canonical directions $d_{i-1},d_i,d_{i+1}$ such that the rays $\rho (p,d_{i-1})$, $\rho (p,d_i)$, and $\rho (p,d_{i+1})$ go into $T_p$. The ray $\rho (p,d_i)$ must therefore make an angle of at least $\alpha /4$ with the edge $e$. Lemma 8 implies that the ray $\rho (p,d_i)$ will hit $\partial C$ before exiting $T_p$. As a result, the direction $d_i$ is good for $p$. Hence, we can apply Lemma 9 to $X$ and conclude that

Summing over all cells $C\in 𝒢$ and using Equation (2) gives

$◀$ As mentioned, the fact that ${\mathrm{\Gamma }}_1\subset \partial P\cap S$ immediately gives us the following corollary.

We now bound the contribution to the perimeter coming from ${\mathrm{\Gamma }}_2$, the part of $\partial R$ that lies in the interior of $P$.

For a grid cell $C\in 𝒢$, let $E_{\mathrm{v}}(C)$ be the set of edges of ${\mathrm{\Gamma }}_2\cap C$ that are mostly vertical, in the sense that their angle with the $x$-axis is at least $\pi /4$. Define $E_{\mathrm{h}}(C)$ analogously for mostly horizontal edges. Note that any edge is mostly vertical or mostly horizontal (or both, when it’s slope is exactly 1).

We prove the bound for $E_{\mathrm{v}}(C)$; the bound for $E_{\mathrm{h}}(C)$ is symmetric. Since $\Vert {\mathrm{\Gamma }}_2\cap C\Vert =\Vert E_{\mathrm{v}}(C)\Vert +\Vert E_{\mathrm{h}}(C)\Vert$, the lemma then follows.

Consider the edges of $E_{\mathrm{v}}(C)$ that bound $R$ from the left, that is, the interior of $R$ lies locally to their right. Let $p$ be a point on such an edge and shoot a ray $\rho$ from $p$ horizontally to the right. We claim that $\rho$ cannot hit another edge of $E_{\mathrm{v}}(C)$ that bounds $R$ from the left before hitting $\partial P$, and thus it either hits $\partial P$ first or exits $C$.

Indeed, if $\rho$ would hit another such edge at a point $q$ before hitting $\partial P$, then the horizontal segment $pq$ is contained in $P$. Hence, $pq$ is a shortest path in $P$ between $p$ and $q$, and because $R$ is geodesically convex, we must have $pq\subseteq R$. This contradicts that $q$ lies on an edge that bounds $R$ from the left.

We now charge any such point $p$ on a left-bounding edge to where the ray $\rho$ hits $\partial P$ (if it hits $\partial P$ first) or to where it exits $C$ (if it does not hit $\partial P$ inside $C$); see Figure 8. This is analogous to the method used in Lemma 9: since we consider mostly vertical edges, we know that $\rho$ forms an angle of at least $\pi /4$ with the corresponding edge of $\partial P$ (whereas in Lemma 9 this bound was $\alpha /4$). Therefore, by using a horizontal decomposition of $P$, we can similarly argue that the total length charged to $\partial P$ is $O(\Vert \partial P\cap C\Vert )$ and the total length charged to $\partial C$ is $O(\mathrm{per}(C))$. In total we have

A similar argument applies to the edges of $E_{\mathrm{v}}(C)$ that bound $R$ from the right. $◀$ Summing the bound from Lemma 12 over all grid cells yields

where the last step uses Lemma 10 and the bound on ${\sum }_{C\in 𝒢}\mathrm{per}(C)$ given in Equation (2).

Since $\mathrm{per}(R)=\Vert {\mathrm{\Gamma }}_1\Vert +\Vert {\mathrm{\Gamma }}_2\Vert$, we conclude that

This proves Theorem 7 with $\nu (\alpha ,\beta )=O\left(\frac{1}{\beta {\alpha }^3}\right)$.

Let $S$ be a point set in a simple polygon $P$. Recall that an $\epsilon$-coreset of $S$ for furthest-neighbor queries is a set $C\subseteq S$ such that for any query point $q\in P$ we have ${\mathrm{dist}}_{\mathrm{g}}(q,\text{fn}(q,C))⩾(1-\epsilon )\cdot {\mathrm{dist}}_{\mathrm{g}}(q,\text{fn}(q,S))$, where $\text{fn}(p,Q)$ denotes the furthest neighbor of $q$ in a set $Q$. By applying Theorem 7 for $R=\text{rch}(S)$, we obtain the following result.

For any query point $q$, its furthest neighbor $\text{fn}(q,S)$ is a vertex of the relative convex hull $\text{rch}(S)$ of $S$ inside $P$ [12]. Moreover, ${\mathrm{dist}}_{\mathrm{g}}(q,\text{fn}(q,S))⩾\frac{1}{2}{\mathrm{diam}}_{\mathrm{g}}(\text{rch}(S))$. Hence, we can compute an $\epsilon$-coreset as follows. First, we compute $\text{rch}(S)$ in $O(n+m\log (n+m))$ time [24, 6, 18]. Then we traverse $\partial \text{rch}(S)$ to select a subset $C$ of $O(1/\epsilon )$ vertices of $\partial \text{rch}(S)$ such that for any vertex $p^{\prime }$ of $\text{rch}(S)$, there is a vertex $p\in C$ whose distance to $p^{\prime }$ along $\partial \text{rch}(S)$ is at most $\frac{\epsilon }{2\nu (\alpha ,\beta )}\cdot \mathrm{per}(\text{rch}(S))$, where $\nu (\alpha ,\beta )$ is the constant in Theorem 7.

To see that $C$ is an $\epsilon$-coreset, recall that $\mathrm{per}(\text{rch}(S))⩽\nu (\alpha ,\beta )\cdot \mathrm{diam}(\text{rch}(S))$ by Theorem 7. Now consider a query point $q$. Let $p$ be a point in $C$ whose distance to $\text{fn}(q,S)$ along $\partial \text{rch}(S)$ is at most $\frac{\epsilon }{2\nu (\alpha ,\beta )}\cdot \mathrm{per}(\text{rch}(S))$. Then ${\mathrm{dist}}_{\mathrm{g}}(p,\text{fn}(q,S))⩽\frac{\epsilon }{2\nu (\alpha ,\beta )}\cdot \mathrm{per}(\text{rch}(S))$, and so

which proves that $C$ is an $\epsilon$-coreset. $◀$

If $S\subset P$ then $m=1$ and the statement is trivial since any two points $x,y\in S\cap P$ can be connected by a segment of length at most $\mathrm{diam}(S)$. Hence, we assume that $\partial P$ intersects the interior of $S$. Let $\mathrm{\ell }$ be the side-length of $S$. We have two cases.

Then, for any $x,y\in S\cap P$,

So in this case we may put all components $C_i$ into a single class and the lemma holds.

Observe that any connected component $C_i$ of $S\cap P$, is a geodesically convex region. Indeed, if there were $x,y\in C_i$ such that a shortest path $\pi (x,y)$ leaves $C_i$, then $\pi (x,y)$ must exit $S$ at a point $a$ and re-enter $S$ at a point $b$. Let $\pi (a,b)\subset \pi (x,y)$ be the subpath of $\pi (x,y)$ from $a$ to $b$. Since $C_i$ is connected, there is a path ${\pi }^{\prime }(a,b)\subset C_i$. Since $P$ is a simple polygon, the cycle ${\pi }^{\prime }(a,b)\cup \pi (a,b)$ does not contain a part of $\partial P$. But then we can replace $\pi (a,b)$ by the part of $\partial S$ that lies inside the cycle, and obtain a shorter path from $x$ to $y$, which is a contradiction. Hence, $C_i$ must be a geodesically convex, as claimed. Applying Theorem 7 with $R:=C_i$ we have $\mathrm{per}(C_i)⩽\nu (\alpha ,\beta )\cdot \mathrm{diam}(C_i)$. Since $C_i\subseteq S$, we have $\mathrm{diam}(C_i)⩽\mathrm{diam}(S)$, and hence for any $x,y\in C_i$