# Minimal Convex Environmental Contours

Åsmund Hausken Sande  Å. H. Sande: Department of Mathematics, University of
Oslo, Moltke Moes vei 35, P.O. Box 1053 Blindern, 0316 Oslo, Norway.
<EMAIL_ADDRESS>and  Johan S. Wind  J. S. Wind: Department of
Mathematics, University of Oslo, Moltke Moes vei 35, P.O. Box 1053 Blindern,
0316 Oslo, Norway<EMAIL_ADDRESS>
###### Abstract.

We develop a numerical method for the computation of a minimal convex and
compact set, $\mathcal{B}\subset\mathbb{R}^{N}$, in the sense of mean width.
This minimisation is constrained by the requirement that
$\max_{b\in\mathcal{B}}\langle b,u\rangle\geq C(u)$ for all unit vectors $u\in
S^{N-1}$ given some Lipschitz function $C$.

This problem arises in the construction of environmental contours under the
assumption of convex failure sets. Environmental contours offer descriptions
of extreme environmental conditions commonly applied for reliability analysis
in the early design phase of marine structures. Usually, they are applied in
order to reduce the number of computationally expensive response analyses
needed for reliability estimation.

We solve this problem by reformulating it as a linear programming problem.
Rigorous convergence analysis is performed, both in terms of convergence of
mean widths and in the sense of the Hausdorff metric. Additionally, numerical
examples are provided to illustrate the presented methods.

This Version :

Keywords: Environmental Contours, Linear Programming, Structural Reliability

MSC2020: 65D18, 90B25, 90C05

##  1\. Introduction

Environmental contours are mathematical tools applied to analyse the
reliability of marine structures, often used in the early design phase of e.g.
ships or oil platforms. They provide a summary statistic of the relevant
environmental factors which reduces the number of computationally expensive
response analyses needed. Due to this, environmental contours are widely used
in reliability analysis of various marine structures [1, 4, 5, 22], and is
listed in the recommended practices - environmental conditions and
environmental loads document by DNV (Det Norske Veritas) [3]. The latter
document provides algorithms for practical computation of environmental
contours, with certain parts relying on heuristic methods. In this article, we
provide algorithms to resolve this issue.

We consider $N$ environmental factors governed by a stochastic process in
$\mathbb{R}^{N}$. A marine structure is then assumed to have a failure set
$\mathcal{F}\subset\mathbb{R}^{N}$ of environmental conditions it cannot
safely handle. Let $\tau_{\mathcal{F}}=\inf\\{t:V_{t}\in\mathcal{F}\\}$ be the
first hitting time of the failure set. Generally, an environmental contour is
the boundary of a set $\mathcal{B}\subset\mathbb{R}^{N}$, representing safe
environmental conditions the structure should withstand. Since the exact shape
of the failure set $\mathcal{F}$ is often unknown in the early design stages,
the environmental contour is chosen to restrain the time to failure,
$\tau_{\mathcal{F}}$, for any failure set $\mathcal{F}$ not overlapping with
the chosen set $\mathcal{B}$. Usually, this restriction comes in the form of
an indirect lower bound on the return period $\mathbb{E}[\tau_{\mathcal{F}}]$.

Note that while this formulation considers failure sets, it is a slight abuse
of terminology. The definition of environmental contours is often decoupled
from the structural response, effectively ignoring it. The response of a
structure to environmental stress is usually considered to be stochastic, even
for fixed environmental conditions. As such, the worst response may randomly
occur outside of $\mathcal{F}$. The formulation in terms of
$\tau_{\mathcal{F}}$ is still used in, or is equivalent to, most definitions
of environmental contours, and more succinctly expresses the underlying ideas
behind environmental contours. For a few examples on how these contours are
connected with structural response in practise we refer to [18, 5]. Both
discuss the use of environmental contours in order to find a singular point,
referred to as the design point, around which the most critical environmental
conditions lie. Based on this point, an importance sampling procedure can be
carried out. It is also worth mentioning that [5] also uses quantiles of the
response distribution along the contour to estimate so-called characteristic
extreme response.

Several methods for defining and computing environmental contours exist, the
most popular of which is the inverse first order reliability method (IFORM)
developed in [8, 23]. For a thorough summary and comparison of different
contour methods we refer to [7, 17], and several models for the environmental
variables along with their resulting contours are compared in [13].

In this article, we will consider methods based on the additional assumption
that all possible failure sets are convex. Several approaches within this
setting exist, such as the method based on direct Monte Carlo simulation
developed in [11, 12]. This method was recently included alongside IFORM in
the aforementioned best practices document for environmental loads by DNV [3],
and has been further studied and extended in several other papers. For
example, convexity properties of the resulting contours, as well as the
inclusion of omission factors, was studied in [10] and the extension of
buffered contours was introduced in [2]. There are also other similar
approaches, such as [9, 14, 21], which consider serial correlation of $V$, and
[19], which extends the theory of [12] to a serially dependent and non-
stationary setting. The common factor of these approaches, is that convexity
of the failure sets allows the requirements on $\mathcal{B}$ to be stated as
minimum outreach requirements. Specifically, all the requirements are lower
bounds on the outreach function of $\mathcal{B}$. The outreach is defined as
$B(\mathcal{B},u)=\max_{b\in\mathcal{B}}\langle b,u\rangle$ for directions $u$
on the standard hypersphere $S^{N-1}$.

The requirements can be succinctly stated as $B(\mathcal{B},u)\geq C(u)$ for
all $u\in S^{N-1}$, where $C$ is some function computed to ensure the desired
restriction of the failure time, usually a lower bound on the return period,
$\mathbb{E}[\tau_{\mathcal{F}}]$. If this inequality holds, we say that
$\partial\mathcal{B}$ is a valid contour. The goal is then to find a valid
contour which is minimal in some sense. Whenever there exists a $\mathcal{B}$
satisfying $B(\mathcal{B},u)=C(u)$, that $\mathcal{B}$ is trivially optimal.
When this is the case, we will refer to $\partial\mathcal{B}$ as a proper
contour. However, a proper contour does not always exist. In [10], they
discuss how estimation errors in $C$ can lead to the absence of proper
contours. To correct this they suggest inflating $C$ by adding a sufficiently
large constant, ensuring that the resulting contour is valid, as well as
proper with respect to the inflated $C$. Similarly, in [6], examples of
distributions for $V$ are given which allow for no proper contours, regardless
of estimation errors. The article also proposes the following method for
constructing valid contours in this setting. They construct an invalid contour
based on $C$, and then extend it in all directions in order to ensure
validity. However, both these methods fail to establish minimal valid contours
in a general sense. The contour is intended to represent the most extreme safe
conditions for a structure. However, if the contour is made too big it imposes
stronger constraints on the class of structures it applies to, thereby
shrinking this class. As such it is of interest to construct contours which
are minimal in some sense, which would allow us to apply the contour, and the
resulting restrictions on $\tau_{\mathcal{F}}$, to as wide a class as
possible.

Our goal in this article is to present a method for constructing valid
contours that are minimal in the sense of mean width (a generalisation of the
perimeter length to more than two dimensions). We show how to solve this by
casting it as a linear programming problem. We prove bounds on the sub-
optimality incurred by discretisation of the continuous problem, and give
convergence results to ensure that our method can find solutions with mean
width arbitrarily close to the optimum.

In Section 2, we provide a simple explanation of our main goal and results for
the two-dimensional case. To proceed, we first cover some necessary
definitions and results in Section 3, before moving on to Section 4, where we
present our main results in a general setting. Specifically, we prove that our
method provides arbitrarily near-optimal solutions. In order to illustrate our
results, we present numerical examples in Section 5. Next, we present several
results that guarantee convergence of our method in the Hausdorff metric in
Section 6. As it turns out that our method can be simplified and improved in
the two-dimensional case, we briefly present the improved method in Section 7.
Finally, as part of our method, we use quadratures for numerical integration
with certain properties. We present some simple constructions for generating
such quadratures in Section 8.

##  2\. Main results in two dimensions

We state our main results in two dimensions here, and wait until the necessary
setup has been made before stating the general result in 4.13. This is only to
give a simplified statement, our method and proofs are developed for general
dimensions.

We are interested in finding the convex, compact shape $\mathcal{B}$ with the
smallest perimeter, which has a given outreach in each direction.
Specifically, the data to our problem is a $L_{C}$-Lipschitz function from the
unit circle to the real numbers, $C\colon S^{1}\to\mathbb{R}$. We denote the
maximum absolute outreach requirement
$\left\|C\right\|_{\infty}\coloneqq\sup_{u\in S^{1}}|C(u)|$. Formally, the
outreach requirement on $\mathcal{B}$ is this: For all directions $u\in
S^{1}$, there exists some $p\in\mathcal{B}$ such that $\langle p,u\rangle\geq
C(u)$.

Numerically, we only access $C$ through a finite number of samples. In two
dimensions, we can sample $m$ evenly spaced directions
$\\{u_{i}\\}_{i=1}^{m}$. If we restrict $\mathcal{B}$ to polygons with sides
perpendicular to the directions $\\{u_{i}\\}_{i=1}^{m}$, and only consider
outreach requirements in those directions, we can formulate the resulting
problem as a linear programming problem (4.5). In two dimensions there is also
a more efficient formulation (7.3). These linear programs can be solved
efficiently using standard techniques, giving an optimal solution
$\widetilde{\mathcal{B}}$ to the discretised problem.

Our theory shows that $\widetilde{\mathcal{B}}$ is nearly an optimal solution
to the continuous problem. Specifically, if we inflate
$\widetilde{\mathcal{B}}$ (in the sense of Lemma 4.7) by a small amount
$\mathcal{O}\left(\frac{1}{m}(L_{C}+\left\|C\right\|_{\infty})\right)$, it is
guaranteed to satisfy the outreach requirements in all directions.
Furthermore, the inflated $\widetilde{\mathcal{B}}$ has a perimeter at most
$\mathcal{O}\left(\frac{1}{m}(L_{C}+\left\|C\right\|_{\infty})\right)$ more
than the optimal perimeter over all convex, compact shapes satisfying the
outreach requirements.

When the number of dimensions is more than two, the perimeter is generalised
to the mean width (3.4), and evenly spaced sample directions are generalised
to $\epsilon$-accurate quadratures (3.6) with low dispersion (3.7). We define
these concepts in the next section.

##  3\. basic intro to needed theory

In this section we will define the main functions we will need throughout the
article.

###  3.1. Standard Notation

As in Section 2 we denote by $\|\cdot\|$ and $\langle\cdot,\cdot\rangle$ the
canonical norm and inner product on $\mathbb{R}^{N}$. Furthermore, the
hypersphere in $\mathbb{R}^{N}$ is defined by
$S^{N-1}=\\{u\in\mathbb{R}^{N}:\|u\|=1\\}$. We will also need the uniform
probability measure on $S^{N-1}$, denoted by $\sigma$.

###  3.2. Convexity

A key concept when dealing with convex sets is their outreach.

######  Definition 3.1.

For any set $\mathcal{B}\subset\mathbb{R}^{N}$ we define the outreach function
of $\mathcal{B}$ as

$B(\mathcal{B},u)=\sup_{b\in\mathcal{B}}\langle b,u\rangle.$

This function is also commonly referred to as the support function of
$\mathcal{B}$.

A closely related concept is the idea of a hyperplane.

######  Definition 3.2.

We define the hyperplane for some $b\in\mathbb{R}$, $u\in S^{N-1}$ as

$\Pi(u,b)=\\{v\in\mathbb{R}^{N}:\langle u,v\rangle=b\\}.$

We further define the half-spaces

$\displaystyle\begin{split}\Pi^{-}(u,b)&=\\{v\in\mathbb{R}^{N}:\langle
u,v\rangle\leq b\\},\\\ \Pi^{+}(u,b)&=\\{v\in\mathbb{R}^{N}:\langle
u,v\rangle\geq b\\}.\end{split}$

Consider then $b\in\mathbb{R}$, $u\in S^{N-1}$, and some non-empty, convex,
and compact $\mathcal{B}\subset\mathbb{R}^{N}$. Since $\mathcal{B}$ is compact
we have that $B(\mathcal{B},u)$ is finite. We can even guarantee some
regularity of $B(\mathcal{B},\cdot)$ by the following result.

######  Proposition 3.3.

Let $\mathcal{B}\subset\mathbb{R}^{N}$ be a non-empty, convex, and compact
set. Denote the maximum radius
$R\coloneqq\sup_{p\in\mathcal{B}}\left\|p\right\|_{2}$. Then
$B(\mathcal{B},u)=\max_{p\in\mathcal{B}}\langle p,u\rangle$ is $R$-Lipschitz
as a function of $u\in S^{N-1}$. Note also $|B(\mathcal{B},u)|\leq R$.

###### Proof.

For fixed $p\in\mathcal{B}$, the function $\langle\cdot,p\rangle$ is
$\left\|p\right\|_{2}$-Lipschitz, hence $R$-Lipschitz. Since
$B(\mathcal{B},u)$ is the supremum of $R$-Lipschitz functions, it is itself
$R$-Lipschitz. ∎

3.3 guarantees that $B(\mathcal{B},\cdot)$ is integrable which allows us to
define our key measure of size for convex compact sets.

######  Definition 3.4.

The width of a a non-empty, convex, and compact set
$\mathcal{B}\subset\mathbb{R}^{N}$ along a vector $u\in S^{N-1}$ can be
written as $B(\mathcal{B},u)-B(\mathcal{B},-u)$. As such, we define the mean
width of $\mathcal{B}$ by

$\int_{S^{N-1}}(B(\mathcal{B},u)-B(\mathcal{B},-u))d\sigma(u).$

Note that this equals

$2\int_{S^{N-1}}B(\mathcal{B},u)d\sigma(u).$

For convex shapes in two dimensions, the mean width is equal to the perimeter
divided by $\pi$.

Lastly, if $B(\mathcal{B},u)\leq b$ we must also have
$\mathcal{B}\subset\Pi^{-}(u,b)$. This leads to the following unique
representation of compact convex sets. This result is a special case of
Theorem 18.8 in [16].

######  Proposition 3.5.

Let $\mathcal{B}\subset\mathbb{R}^{N}$ be convex and compact, we then have

$\mathcal{B}=\bigcap_{u\in S^{N-1}}\Pi^{-}(u,B(\mathcal{B},u)).$

###  3.3. Numerical Definitions

In order to compute the mean width our convex sets we will need to employ a
numerical integration method providing universal bounds on the integration
error. To address this we introduce the following.

######  Definition 3.6.

We say a set of points and weights $\\{(u_{i},w_{i})\\}_{i=1}^{m}\subset
S^{N-1}\times[0,\infty)$ is an $\epsilon$-accurate quadrature, if the
following holds for all $L$-Lipschitz continuous functions $f\colon
S^{N-1}\to\mathbb{R}$. For all functions $f$ satisfying $|f(u)-f(v)|\leq
L\left\|u-v\right\|_{2}$ for all $u,v\in S^{N-1}$, we have

$\displaystyle\left|\int_{S}f(u)\,d\sigma(u)-\sum_{i=1}^{m}f(u_{i})w_{i}\right|\leq\epsilon(L+\left\|f\right\|_{\infty}).$
(3.1)

In order to control this error we will also need a related concept
characterising the spread of some finite $\mathcal{S}\subset S^{N-1}$.

######  Definition 3.7.

We define the dispersion of a set $\mathcal{S}\subset S^{N-1}$ by

$\mathrm{disp}(\mathcal{S})=\sup_{u\in S^{N-1}}\inf_{v\in\mathcal{S}}\|u-v\|.$

######  Remark 3.8.

In order to carry out the numerical integration necessary in this paper, we
consider a general grid $\mathcal{S}=\\{u_{i}\\}_{i=1}^{m}\subset S^{N-1}$ and
set of weights $W=\\{w_{i}\\}_{i=1}^{m}$, with some constraints on
$\mathrm{disp}(\mathcal{S})$ and the accuracy of
$\\{(u_{i},w_{i})\\}_{i=1}^{m}$. However, we also give specific constructions
of $\epsilon$-accurate quadratures in Section 8.

##  4\. Minimal Valid Contours

In this section, we aim to compute minimal valid contours in the sense of mean
width. To set the scene. We will start by defining relevant concepts about our
original and approximating discrete problem, for then to present several
results guaranteeing control over estimation errors.

###  4.1. The Continuous Problem

The main problem we want to solve can be precisely formulated as follows.

minimise $\displaystyle\int_{S^{N-1}}B(\mathcal{B},u)d\sigma(u)$ (4.1) subject
to $\displaystyle B(\mathcal{B},\cdot)\geq C(\cdot),$ (4.2)
$\displaystyle\mathcal{B}\text{ convex and compact.}$

To examine this problem, we introduce the following notation.

######  Definition 4.1.

We denote the set of feasible solutions to the continuous problem (4.1) by

$\mathcal{C}^{\infty}=\left\\{\mathcal{B}\subset\mathbb{R}^{N}\mid\mathcal{B}\text{
convex and compact, }B(\mathcal{B},\cdot)\geq C(\cdot)\right\\}.$

The optimal value of the objective function is denoted by

$V^{CP}=\inf\left\\{\int_{S^{N-1}}B(\mathcal{B},u)d\sigma(u),\,\mathcal{B}\in\mathcal{C}^{\infty}\right\\}.$

Lastly, we define the $\gamma$-near optimal solution space by

$\mathcal{C}^{\gamma}=\left\\{\mathcal{B}\in\mathcal{C}^{\infty}\Big{|}\int_{S^{N-1}}B(\mathcal{B},u)d\sigma(u)-V^{CP}\leq\gamma\right\\}.$

It turns out that this problem has an optimal solution under our running
assumption that $C$ is continuous. This result is proven through consideration
of the Hausdorff metric, as such the proof is relegated to 6.3 in Section 6.

###  4.2. The Discrete Problem

In what follows, we will consider a way of approximating optimal contours. To
achieve this, we will need to employ numerical methods, which necessitate
discretisation. Therefore, we also consider valid environmental contours with
respect to some (usually finite) sub-collection of unit vectors
$\mathcal{S}\subseteq S^{N-1}$.

We will say that $\partial\mathcal{B}$ is $(\mathcal{S},C)$-valid if
$\mathcal{B}$ is convex, compact, and for all $u\in\mathcal{S}$ we have
$B(\mathcal{B},u)\geq C(u)$.

If we take any $\mathcal{S}=\\{u_{i}\\}_{i=1}^{m}$ and a
$(\mathcal{S},C)$-valid contour $\partial\mathcal{B}$, then for every
$u_{i}\in\mathcal{S}$ there must be some $p_{i}\in\mathcal{B}$ such that
$\langle p_{i},u_{i}\rangle=B(\mathcal{B},u_{i})$, which implies

$\langle p_{i},u_{i}\rangle\geq C(u_{i})\text{ for }i=1,2,\dots,m.$ (4.3)

Furthermore, since for all $i$ we have $p_{i}\in\mathcal{B}$, we must also
have

$\langle p_{i},u_{j}\rangle\leq B(\mathcal{B},u_{j})\text{ for
}i,j=1,2,\dots,m.$ (4.4)

Conversely, assume we have a set of points $\\{p_{i}\\}_{i=1}^{m}$ satisfying
(4.3) and (4.4) for some convex and compact set $\mathcal{B}$. By (4.4) we
know that $\\{p_{i}\\}_{i=1}^{m}\subset\mathcal{B}$, which implies by (4.3)
that $B(\mathcal{B},u_{i})\geq C(u_{i})$ for all $i$, which means that
$\partial\mathcal{B}$ is $(\mathcal{S},C)$-valid.

Consequently, there is a correspondence between $(\mathcal{S},C)$-valid
contours and sets of points, $\\{p_{i}\\}_{i=1}^{m}$. Hence, we consider the
following linear programming problem. Note that in order to approximate
optimisation in mean width, we will refer to this as the linear program based
on $(\mathcal{S},W)$ where $W=(w_{i})_{i=1}^{m}$ is a set of weights such that
$\\{(u_{i},w_{i})\\}_{i=1}^{m}$ forms an $\epsilon$-accurate quadrature for
some $\epsilon\in\mathbb{R}_{+}$.

minimise $\displaystyle\sum_{i=1}^{m}w_{i}B_{i}$ (4.5) subject to
$\displaystyle\langle p_{i},u_{i}\rangle\geq C(u_{i})$ $\displaystyle
i=1,2,\dots,m$ $\displaystyle\langle p_{i},u_{j}\rangle\leq B_{j}$
$\displaystyle i,j=1,2,\dots,m$ $\displaystyle p_{i}\in\mathbb{R}^{N}$
$\displaystyle i=1,2,\dots,m$ $\displaystyle u_{i}\in S^{N-1}$ $\displaystyle
i=1,2,\dots,m$ $\displaystyle C(u_{i}),B_{i}\in\mathbb{R}$ $\displaystyle
i=1,2,\dots,m$

We then note two facts about this problem. Firstly, the values
$p_{i}=\|C\|_{\infty}u_{i}$, $B_{i}=\|C\|_{\infty}$ for all $i$ with
$\|C\|_{\infty}=\max_{u\in S^{N-1}}|C(u)|$, satisfies the constraints and
provides a feasible solution. Secondly, since
$\sum_{i=1}^{m}w_{i}B_{i}\geq\sum_{i=1}^{m}w_{i}C(u_{i})>-\infty$, the
objective function is bounded. Combining these facts we know that the problem
must have at least one optimal solution, which yields a minimal
$(\mathcal{S},\mathcal{C})$-valid contour by the either of the following two
constructions.

######  Proposition 4.2.

Consider the linear programming problem (4.5), with an optimal solution
$\left(\left(p^{*}_{i}\right)_{i=1}^{m},\,\left(B^{*}_{i}\right)_{i=1}^{m}\right)$.
If $\operatorname{convh}(\cdot)$ denotes the convex hull we have that

$\mathcal{B}^{*}=\operatorname{convh}\left(\left\\{p^{*}_{i}\right\\}_{i=1}^{m}\right),$

defines a $(\mathcal{S},C)$-valid contour with
$B(\mathcal{B}^{*},u_{i})=B_{i}$ for all $i$.

###### Proof.

Firstly, we note that every $b\in\mathcal{B}^{*}$ is a convex combination of
the $p^{*}_{i}$s. This means $b$ has the representation
$b=\sum_{i=1}^{m}a_{i}(b)p_{i}$ where $\sum_{i=1}^{m}a_{i}(b)=1,\,a_{i}\geq
0$, which implies

$\displaystyle B(\mathcal{B}^{*},u_{i})$
$\displaystyle=\max_{b\in\mathcal{B}^{*}}\langle b,u_{i}\rangle$
$\displaystyle=\max_{b\in\mathcal{B}^{*}}\sum_{k=1}^{m}a_{k}(b)\langle
p_{k},u_{i}\rangle$ $\displaystyle\leq\max_{j}\langle
p_{j},u_{i}\rangle\max_{b\in\mathcal{B}^{*}}\sum_{k=1}^{m}a_{k}(b)$
$\displaystyle=\max_{j}\langle p_{j},u_{i}\rangle.$

Conversely, since
$\left\\{p^{*}_{i}\right\\}_{i=1}^{m}\subseteq\mathcal{B}^{*}$ we have
$\max_{j}\langle p_{j},u_{i}\rangle\leq B(\mathcal{B}^{*},u_{i})$ which
implies $B(\mathcal{B}^{*},u_{i})=\max_{j}\langle p_{j},u_{i}\rangle$.

As a consequence we get

$B(\mathcal{B}^{*},u_{i})\geq\langle p_{i},u_{i}\rangle\geq C(u_{i}).$

As the convex hull of a finite number of points, $\mathcal{B}^{*}$, is compact
and convex. These facts make $\partial\mathcal{B}^{*}$ a
$(\mathcal{S},C)$-valid contour. ∎

######  Corollary 4.3.

Consider the linear programming problem (4.5), with an optimal solution
$\left(p_{i}\right)_{i=1}^{m},\,\left(B_{i}\right)_{i=1}^{m}$. We then have
that

$\mathcal{B}^{\prime}=\bigcap_{i=1}^{m}\Pi^{-}(u_{i},B_{i}),$

defines a $(\mathcal{S},C)$-valid contour with
$B(\mathcal{B}^{\prime},u_{i})=B_{i}$ for all $i$.

###### Proof.

We first note that since $\langle p_{i},u_{j}\rangle\leq B_{j}$ for all $i,j$,
we must have $p_{i}\in\mathcal{B}^{\prime}$ for all $i$. This implies that
when $\mathcal{B}^{*}$ is as defined in 4.2, we have
$\mathcal{B}^{*}\subseteq\mathcal{B}^{\prime}$ since $\mathcal{B}^{\prime}$ is
convex. This immediately implies that $\partial\mathcal{B}^{\prime}$ is
$(\mathcal{S},C)$-valid. ∎

Similarly to 4.1, we consider the analogous concepts for this discrete
problem, which will aid our comparison between the continuous problem (4.1)
and our discrete approximation (4.5).

######  Definition 4.4.

We denote the set of valid solutions to the discrete problem (4.5) based on
$(\mathcal{S},W)$ by

$\mathcal{D}^{\infty}(\mathcal{S},W)=\left\\{\mathcal{B}\subset\mathbb{R}^{N}\mid\mathcal{B}\text{
convex and compact, }B(\mathcal{B},u)\geq C(u)\text{ for all
}u\in\mathcal{S}\right\\}.$

The optimal value of the objective function is denoted by

$V^{DP}(\mathcal{S},W)=\min\left\\{\sum_{i=1}^{m}w_{i}B(\mathcal{B},u_{i}),\,\mathcal{B}\in\mathcal{D}^{\infty}\right\\}.$

Lastly, we define the $\gamma$-near optimal solution space by

$\mathcal{D}^{\gamma}(\mathcal{S},W)=\left\\{\mathcal{B}\in\mathcal{C}^{\infty}\Big{|}\sum_{i=1}^{m}w_{i}B(\mathcal{B},u_{i})-V^{DP}\leq\gamma\right\\}.$

We will usually omit the dependence on $(\mathcal{S},W)$ whenever the meaning
is clear or otherwise superfluous.

######  Remark 4.5.

If we consider any $\mathcal{B}\in\mathcal{D}^{\infty}$ then we know from
previous arguments that there exists a feasible solution
$\left(\left(p_{i}\right)_{i=1}^{m},\,\left(B_{i}\right)_{i=1}^{m}\right)$
with $\left\\{p_{i}\right\\}_{i=1}^{m}\subset\mathcal{B}$ and
$B_{i}=B(\mathcal{B},u_{i})$. Consequently, if $B^{*}$ and $B^{\prime}$ are
defined as in 4.2 and Corollary 4.3, we see that
$\mathcal{B}^{*}\subseteq\mathcal{B}\subseteq\mathcal{B}^{\prime}$, which
means that the constructions of $\mathcal{B}^{*}$ and $\mathcal{B}^{\prime}$
provide lower and upper bounds on all sets in $\mathcal{D}^{\infty}$.

###  4.3. Convergence and Near-Optimality

With these definitions established, we can more accurately state the goal of
this chapter. We first aim to show how one can construct $(S^{N-1},C)$-valid
contours from any $\mathcal{B}\in\mathcal{D}^{\gamma}$ for some $\gamma\geq
0$. Furthermore, we will prove that the optimal value of the discrete problem,
$V^{DP}$, can arbitrarily well approximate $V^{CP}$. Using this, we get
explicit upper bounds on the near-optimality of the constructed
$(S^{N-1},C)$-valid contours.

In order to control the near-optimality of solutions to our discrete problems,
we need to consider two issues. The first problem we will tackle is the fact
that a $(\mathcal{S},C)$-valid contour is not necessarily $(S^{N-1},C)$-valid.
To amend this, we will consider a method for inflating contours to ensure
their validity. Secondly, we will need to correct for the fact that (4.5)
optimises for an approximation of mean width, this can be handled by
explicitly including the numerical error from discrete integration of the mean
width.

To construct valid contours from our discrete approximation, we will first
need a bound on how much a contour $\partial\mathcal{B}$ with
$\mathcal{B}\in\mathcal{D}^{\infty}$ can violate the constraint of
$B(\mathcal{B},\cdot)\geq C(\cdot)$.

######  Lemma 4.6.

Fix some $\mathcal{S}\subset S^{N-1}$ with $\delta=\mathrm{disp}(\mathcal{S})$
and let $\mathcal{B}\in\mathcal{D}^{\infty}$. Then for all $u\in S^{N-1}$, we
have

$C(u)-\delta(L_{C}+R)\leq B(\mathcal{B},u),$

where $L_{C}$ is the Lipschitz constant of $C$, and
$R=\max_{p\in\mathcal{B}}\|p\|$.

###### Proof.

Consider any $u\in S^{N-1}$ and pick some $v\in\mathcal{S}$ such that
$\|u-v\|\leq\delta$. This immediately yields by the Lipschitz continuity of
$C$ that $|C(u)-C(v)|\leq\delta L_{C}$. We then choose some
$p_{v}\in\partial\mathcal{B}$ such that $\langle
p_{v},v\rangle=B(\mathcal{B},v)\geq C(v)$ and get

$\displaystyle B(\mathcal{B},u)$ $\displaystyle\geq\langle p_{v},u\rangle$
$\displaystyle=\langle p_{v},v\rangle+\langle p_{v},u-v\rangle$
$\displaystyle\geq C(v)-\delta\|p_{v}\|$ $\displaystyle\geq C(u)-\delta
L_{C}-\delta R$ $\displaystyle=C(u)-\delta(L_{C}+R).$

∎

With this result, we can quantify how far our $(\mathcal{S},C)$-valid contours
are from being $(S^{N-1},C)$-valid. The main idea in constructing
$(S^{N-1},C)$-valid contours is to use the bound of Lemma 4.6, and then use
following result to inflate the contour.

######  Lemma 4.7.

Assume we have a subset $\mathcal{S}\subseteq S^{N-1}$ and a convex and
compact set $\mathcal{B}$. If we then define

$\mathcal{B}^{e}=\bigcap_{v\in\mathcal{S}}\Pi^{-}\left(v,B(\mathcal{B},v)+e\right),$

we have that $B(\mathcal{B}^{e},u)\geq B(\mathcal{B},u)+e$ for all $u\in
S^{N-1}$, and $B(\mathcal{B}^{e},v)=B(\mathcal{B},v)+e$ for all
$v\in\mathcal{S}$.

###### Proof.

For any $u\in S^{N-1}$ there exists a $b(u)\in\mathcal{B}$ such that $\langle
b(u),u\rangle=B(\mathcal{B},u)$, we then have immediately that $\langle
b(u)+eu,u\rangle=B(\mathcal{B},u)+e$. Furthermore, since $b(u)\in\mathcal{B}$,
we have for every $v\in\mathcal{S},\,u\in S^{N-1}$ that $\langle
b(u),v\rangle\leq B(\mathcal{B},v)$ which further yields

$\langle b(u)+eu,v\rangle\leq B(\mathcal{B},v)+e\langle u,v\rangle\leq
B(\mathcal{B},v)+e.$

As a consequence, we must have $b(u)+eu\in\mathcal{B}^{e}$, which implies
$B(\mathcal{B}^{e},u)\geq B(\mathcal{B},u)+e$ for all $u\in S^{N-1}$. Lastly,
by definition of $\mathcal{B}^{e}$, we have $B(\mathcal{B}^{e},v)\leq
B(\mathcal{B},v)+e$ for any $v\in\mathcal{S}$, which coupled with the previous
inequality implies that $B(\mathcal{B}^{e},v)=B(\mathcal{B},v)+e$ for all
$v\in\mathcal{S}$. ∎

These results imply that for any $\gamma\geq
0,\,\mathcal{B}\in\mathcal{D}^{\gamma}$, we may inflate the contour in order
to guarantee that the resulting $\mathcal{B}^{e}$ provides a
$(S^{N-1},C)$-valid contour. Note that this construction depends on
$\max_{p\in\mathcal{B}}\|p\|$. In order to extend these results and guarantee
universal bounds on the necessary inflation, we will need the following
results which limit the size of $\max_{p\in\mathcal{B}}\|p\|$ for all
$\mathcal{B}$ in $\mathcal{D}^{\gamma}$. However, to achieve this bound we
will first need a small technical computation.

######  Lemma 4.8.

For any $v\in S^{N-1}$, we have

$\int_{S^{N-1}}\langle v,u\rangle^{+}d\sigma(u)\geq\frac{1}{3\sqrt{N}},$

where $(\cdot)^{+}$ denotes $\max(\cdot,0)$.

###### Proof.

We rewrite as an expectation of absolute values as follows

$\displaystyle\int_{S^{N-1}}\langle v,u\rangle^{+}d\sigma(u)$
$\displaystyle=\frac{1}{2}\mathbb{E}_{u\in\mathrm{Unif}(S^{N-1})}\left(|\langle
v,u\rangle|\right)$
$\displaystyle=\frac{\mathbb{E}_{z\in\mathcal{N}(0,I_{N})}\left\|z\right\|\,\mathbb{E}_{u\in\mathrm{Unif}(S^{N-1})}\left(|\langle
v,u\rangle|\right)}{2\mathbb{E}_{z\in\mathcal{N}(0,I_{N})}\left\|z\right\|}.$

Noting that the multivariate normal distribution has uniformly random
direction, we may calculate the numerator as

$\displaystyle\mathbb{E}_{z\in\mathcal{N}(0,I_{N})}\left\|z\right\|\,\mathbb{E}_{u\in\mathrm{Unif}(S^{N-1})}\left(|\langle
v,u\rangle|\right)=$
$\displaystyle\mathbb{E}_{z\in\mathcal{N}(0,I_{N})}\left(|\langle
v,z\rangle|\right)=\mathbb{E}_{z_{1}\in\mathcal{N}(0,1)}|z_{1}|=\sqrt{\frac{2}{\pi}}.$

The denominator can be bounded by
$2\mathbb{E}_{z\in\mathcal{N}(0,I_{N})}\left\|z\right\|\leq
2\sqrt{\mathbb{E}_{z\in\mathcal{N}(0,I_{N})}\left\|z\right\|^{2}}=2\sqrt{N}$.
In total, we get

$\displaystyle\int_{S^{N-1}}\langle v,u\rangle^{+}d\sigma(u)$
$\displaystyle\geq\frac{\sqrt{\frac{2}{\pi}}}{2\sqrt{N}}>\frac{1}{3\sqrt{N}}.$

∎

######  Lemma 4.9.

Let $\mathcal{B}$ be a compact set satisfying
$\max_{p,q\in\mathcal{B}}\|p-q\|\geq K$ for some $K\in\mathbb{R}^{+}$. We then
have that the halved mean width of $\mathcal{B}$ satisfies

$\int_{S^{N-1}}B(\mathcal{B},u)d\sigma(u)\geq{\frac{K}{3\sqrt{N}}}.$

###### Proof.

We start by picking $p_{0},p\in\mathcal{B}$ such that $\|p-p_{0}\|\geq K$ and
note that

$B(\mathcal{B},u)\geq\max(\langle p,u\rangle,\langle p_{0},u\rangle)=\langle
p-p_{0},u\rangle^{+}+\langle p_{0},u\rangle.$

If we then note that $\int_{S^{N-1}}\langle p_{0},u\rangle d\sigma(u)=0$, we
can define $v=\frac{p-p_{0}}{|p-p_{0}|}$ to get

$\int_{S^{N-1}}B(\mathcal{B},u)d\sigma(u)\geq\int_{S^{N-1}}\left(\langle
p-p_{0},u\rangle^{+}+\langle
p_{0},u\rangle\right)d\sigma(u)=K\int_{S^{N-1}}\langle
v,u\rangle^{+}d\sigma(u).$

By Lemma 4.8 this implies the desired result. ∎

With these results, we can now universally bound $\max_{p\in\mathcal{B}}\|p\|$
for all $\mathcal{B}$ in $\mathcal{D}^{\gamma}$, which will also provide a
universal bound on the amount of inflation needed in Lemma 4.7 to yield a
$(S^{N-1},C)$-valid contour.

######  Lemma 4.10.

Assume that $\\{(u_{i},w_{i})\\}_{i=1}^{m}\subset\mathcal{S}\times[0,\infty)$
is an $\epsilon$-accurate quadrature with
$\delta\coloneqq\mathrm{disp}(\mathcal{S})$ satisfying
$\epsilon,\delta\leq\frac{1}{10\sqrt{N}}$. Furthermore, let
$\mathcal{B}\in\mathcal{D}^{\gamma}$, then

$\max_{p\in\mathcal{B}}\|p\|\leq 12\sqrt{N}(\|C\|_{\infty}+\gamma).$

###### Proof.

First, we pick some $p_{max}\in\partial\mathcal{B}$ such that
$\|p_{max}\|=\max_{p\in\mathcal{B}}\|p\|$. If $\|p_{max}\|=0$ then the desired
bound holds trivially. As such we assume, without loss of generality, that
$\|p_{max}\|>0$ and define $w={p_{max}}/{\|p_{max}\|}$. We then consider some
$v\in\mathcal{S}$ such that $\|(-w)-v\|\leq\delta$ and note that there must be
some $p_{0}\in\partial\mathcal{B}$ such that $\langle
p_{0},v\rangle=B(\mathcal{B},v)\geq C(v)\geq-\|C\|_{\infty}$. This means that

$\displaystyle\langle p_{0},w\rangle$ $\displaystyle=\langle
p_{0},w+v\rangle-\langle p_{0},v\rangle$
$\displaystyle\leq\delta\|p_{0}\|+\|C\|_{\infty}$
$\displaystyle\leq\delta\|p_{max}\|+\|C\|_{\infty},$

which further yields

$\|p_{max}-p_{0}\|\geq\langle
p_{max}-p_{0},w\rangle\geq\|p_{max}\|(1-\delta)-\|C\|_{\infty}.$

This means that

$\max_{p,q\in\mathcal{B}}\|p-q\|\geq\|p_{max}\|(1-\delta)-\|C\|_{\infty},$

which, by Lemma 4.9, gives

$\int_{S^{N-1}}B(\mathcal{B},u)d\sigma(u)\geq\frac{\|p_{max}\|(1-\delta)-\|C\|_{\infty}}{3\sqrt{N}}.$

On the other hand, since $p_{i}=\|C\|_{\infty}u_{i}$, $B_{i}=\|C\|_{\infty}$
for all $i$ is a feasible solution of the linear program, we must also have

$\sum_{i=1}^{m}w_{i}B(\mathcal{B},u_{i})\leq
V^{DP}+\gamma\leq\sum_{i=1}^{m}w_{i}C(u_{i})+\gamma\leq(1+\epsilon)\|C\|_{\infty}+\gamma.$

Finally, by 3.3 and the definition of an $\epsilon$-accurate quadrature, we
have that

$\left|\int_{S^{N-1}}B(\mathcal{B},u)d\sigma(u)-\sum_{i=1}^{m}w_{i}B(\mathcal{B},u_{i})\right|\leq
2\epsilon\|p_{max}\|.$

Putting these facts together, we get

$\displaystyle(1+\epsilon)\|C\|_{\infty}+\gamma$
$\displaystyle\geq\sum_{i=1}^{m}w_{i}B(\mathcal{B},u_{i})$
$\displaystyle\geq\int_{S^{N-1}}B(\mathcal{B},u)d\sigma(u)-2\epsilon\|p_{max}\|$
$\displaystyle\geq\frac{\|p_{max}\|(1-\delta)-\|C\|_{\infty}}{3\sqrt{N}}-2\epsilon\|p_{max}\|.$

Using the assumptions $\epsilon,\delta\leq\frac{1}{10\sqrt{N}}$ and $N\geq 2$,
we get

$\max_{p\in\mathcal{B}}\|p\|\leq\frac{3\sqrt{N}((1+\epsilon)\|C\|_{\infty}+\gamma)+\|C\|_{\infty}}{1-\delta-6\sqrt{N}\epsilon}\leq
12\sqrt{N}(\|C\|_{\infty}+\gamma).$

∎

Combining Lemmas 4.6, 4.10 and 4.7, we can construct $(S^{N-1},C)$-valid
contours from our discrete approximation. This allows us to directly compare
our discrete solutions from (4.5) to the theoretical ones of (4.1). However,
we still need to address the error stemming from the numerical integration of
$B(\mathcal{B},\cdot)$. To handle this, we note that the integration error of
an $\epsilon$-accurate quadrature involves $\max_{p\in\mathcal{B}}\|p\|$,
which is bounded for $\mathcal{B}\in\mathcal{D}^{\gamma}$ by Lemma 4.10. To
finish our preparations for the main theorem, we prove the analogous result
for $\mathcal{B}\in\mathcal{C}^{\gamma}$.

######  Corollary 4.11.

Assume $\mathcal{B}\in\mathcal{C}^{\gamma}$ for some $\gamma\geq 0$, we then
have that

$\max_{p\in\mathcal{B}}\|p\|\leq 4\sqrt{N}\left(\|C\|_{\infty}+\gamma\right),$

where $\|C\|_{\infty}=\max_{u\in S^{N-1}}|C(u)|$.

###### Proof.

First, we pick some $p_{max}\in\mathcal{B}$ such that
$\|p_{max}\|=\max_{p\in\mathcal{B}}\|p\|$. If $\|p_{max}\|=0$ then the desired
bound holds trivially. As such we assume, without loss of generality, that
$\|p_{max}\|>0$ and define $v=p_{max}/\|p_{max}\|$. Since
$\partial\mathcal{B}$ is $(S^{N-1},C)$-valid, there must also exist some
$p_{0}\in\partial\mathcal{B}$ such that $\langle p_{0},-v\rangle\geq
C(-v)\geq-\|C\|_{\infty}$, which implies

$\displaystyle\|p_{max}-p_{0}\|$ $\displaystyle\geq\langle
p_{max}-p_{0},v\rangle=\langle p_{max},v\rangle+\langle
p_{0},-v\rangle\geq\|p_{max}\|-\|C\|_{\infty}.$

As a consequence, we note that since
$\max_{p,q\in\mathcal{B}}\|p-q\|\geq\|p_{max}\|-\|C\|_{\infty}$, Lemma 4.9
implies that

$\int_{S^{N-1}}B(\mathcal{B},u)d\sigma(u)\geq\frac{\|p_{max}\|-\|C\|_{\infty}}{3\sqrt{N}}.$

Furthermore, we have that $\|C\|_{\infty}S^{N-1}\in\mathcal{C}^{\infty}$ which
means that $V^{CP}\leq\|C\|_{\infty}$ and therefore
$\mathcal{B}\in\mathcal{C}^{\gamma}$ implies
$\int_{S^{N-1}}B(\mathcal{B},u)d\sigma(u)\leq\|C\|_{\infty}+\gamma$.

Combining these facts with $N\geq 1$ yields

$\|p_{max}\|\leq 3\sqrt{N}(\|C\|_{\infty}+\gamma)+\|C\|_{\infty}\leq
4\sqrt{N}(\|C\|_{\infty}+\gamma).$

∎

With these universal bounds established, we can discuss the two main results
of this chapter, which guarantee that our discrete problem (4.5) indeed
approximates (4.1).

######  Theorem 4.12.

Fix some $\epsilon$-accurate quadrature $\\{(u_{i},w_{i})\\}_{i=1}^{m}$ and
assume that $\mathcal{S}=\\{u_{i}\\}_{i=1}^{m}$ with
$\delta=\mathrm{disp}(\mathcal{S})$ satisfies
$\epsilon,\delta\leq\frac{1}{10\sqrt{N}}$. Then

$\displaystyle V^{CP}-V^{DP}$ $\displaystyle\leq
12\sqrt{N}\|C\|_{\infty}(2\epsilon+\delta)+L_{C}\delta,$ $\displaystyle
V^{DP}-V^{CP}$ $\displaystyle\leq 8\sqrt{N}\|C\|_{\infty}\epsilon.$

###### Proof.

For the first statement, let
$\left(\left(p^{*}_{i}\right)_{i=1}^{m},\,\left(B^{*}_{i}\right)_{i=1}^{m}\right)$
be an optimal solution of the linear programming problem (4.5) and choose any
$\mathcal{B}^{DP}\in\mathcal{D}^{0}$ with
$B(\mathcal{B}^{DP},u_{i})=B^{*}_{i}$ for $i=1,2,\dots,m$. We then denote
$R^{DP}=\max_{p\in\mathcal{B}^{DP}}\|p\|$ and note that 3.3 along with the
definition of an $\epsilon$-accurate quadratures imply

$\left|\sum_{i=1}^{m}w_{i}B^{*}_{i}-\int_{S^{N-1}}B(\mathcal{B}^{DP},u)d\sigma(u)\right|\leq
2\epsilon R^{DP}.$

By Lemma 4.6, we know $C(u)-\delta(L_{C}+R^{DP})\leq B(\mathcal{B}^{DP},u),$
which motivates us to define $\mathcal{B}^{e}$ as

$\mathcal{B}^{e}=\bigcap_{u\in
S^{N-1}}\Pi^{-}\left(u,B(\mathcal{B}^{DP},u)+\delta(L_{C}+R^{DP})\right).$

By Lemma 4.7 we know that
$B(\mathcal{B}^{e},u)=B(\mathcal{B}^{DP},u)+\delta(L_{C}+R^{DP})\geq C(u)$ for
all $u\in S^{N-1}$. This yields firstly that

$\int_{S^{N-1}}B(\mathcal{B}^{e},u)d\sigma(u)=\int_{S^{N-1}}B(\mathcal{B}^{DP},u)d\sigma(u)+\delta(L_{C}+R^{DP}).$

Secondly, it implies that $\mathcal{B}^{e}$ is a feasible solution for the
continuous problem, and therefore

$\displaystyle V^{CP}$
$\displaystyle\leq\int_{S^{N-1}}B(\mathcal{B}^{e},u)d\sigma(u)$
$\displaystyle=\int_{S^{N-1}}B(\mathcal{B}^{DP},u)d\sigma(u)+\delta(L_{C}+R^{DP})$
$\displaystyle\leq\sum_{i=1}^{m}w_{i}B^{*}_{i}+2\epsilon
R^{DP}+\delta(L_{C}+R^{DP})$ $\displaystyle=V^{DP}+2\epsilon
R^{DP}+\delta(L_{C}+R^{DP}).$

Combining with Lemma 4.10, this implies $V^{CP}-V^{DP}\leq
12\sqrt{N}\|C\|_{\infty}(2\epsilon+\delta)+\delta L_{C}$.

As for the other direction, we consider some optimal solution of the
continuous problem $\mathcal{B}^{CP}$ and denote
$R^{CP}=\max_{p\in\mathcal{B}^{CP}}\|p\|$. We know that for all
$i=1,2,\dots,m$ there is some $p_{i}^{CP}\in\mathcal{B}^{CP}$ such that
$\langle p_{i}^{CP},u_{i}\rangle\geq C(u_{i})$. This means that
$\left(\left(p^{CP}_{i}\right)_{i=1}^{m},\,\left(B(\mathcal{B}^{CP},u_{i})\right)_{i=1}^{m}\right)$
is a feasible solution of the linear programming problem. As a consequence, we
have

$\displaystyle V^{DP}$
$\displaystyle\leq\sum_{i=1}^{m}w_{i}B(\mathcal{B}^{CP},u_{i})$
$\displaystyle\leq\int_{S^{N-1}}B(\mathcal{B}^{CP},u)d\sigma(u)+2\epsilon
R^{CP}$ $\displaystyle=V^{CP}+2\epsilon R^{CP},$

which concludes the proof by recalling that Corollary 4.11 says $R^{CP}\leq
4\sqrt{N}\|C\|_{\infty}.$ ∎

This means that we can arbitrarily well approximate $V^{CP}$ by considering
the linear programming problem (4.5). As a consequence of this result, we can
also guarantee that the $(S^{N-1},C)$-valid contours constructed using Lemma
4.7 can be made universally near-optimal in terms of the original continuous
problem (4.1), by means of the following result.

######  Theorem 4.13.

Fix some $\epsilon$-accurate quadrature $\\{(u_{i},w_{i})\\}_{i=1}^{m}$ and
assume that $\mathcal{S}=\\{u_{i}\\}_{i=1}^{m}$ with
$\delta=\mathrm{disp}(\mathcal{S})$ satisfies
$\epsilon,\delta\leq\frac{1}{10\sqrt{N}}$. Let
$e=\delta\big{(}L_{C}+12\sqrt{N}(\|C\|_{\infty}+\gamma)\big{)}$ and define
$\mathcal{B}^{e}=\bigcap_{u\in\mathcal{S}}\Pi^{-}\left(u,B(\mathcal{B},u)+e)\right)$
for any $\mathcal{B}\in\mathcal{D}^{\gamma}$, $\gamma\geq 0$.

We then have

$\mathcal{B}^{e}\in\mathcal{C}^{\gamma+\beta},$

where $\beta=4e+32\sqrt{N}(\|C\|_{\infty}+\gamma)\,\epsilon$.

###### Proof.

We know from Lemmas 4.6, 4.7 and 4.10 that $\mathcal{B}^{e}$ satisfies

$B(\mathcal{B}^{e},u)\geq B(\mathcal{B},u)+e\\\ \geq\big{(}C(u)-e\big{)}+e\\\
=C(u),$

for all $u\in S^{N-1}$, which implies
$\mathcal{B}^{e}\in\mathcal{C}^{\infty}$. Furthermore, we have

$\sum_{i=1}^{m}w_{i}B(\mathcal{B}^{e},u_{i})=\sum_{i=1}^{m}w_{i}\big{(}B(\mathcal{B},u_{i})+e\big{)}\leq
V^{DP}+\gamma+(1+\epsilon)e,$

which yields $\mathcal{B}^{e}\in\mathcal{D}^{\gamma+(1+\epsilon)e}$. This,
along with the definition of $\epsilon$-accurate quadratures, 3.3 and Lemma
4.10, implies

$\left|\sum_{i=1}^{m}w_{i}B(\mathcal{B}^{e},u_{i})-\int_{S^{N-1}}B(\mathcal{B}^{e},u)d\sigma(u)\right|\leq
24\sqrt{N}\Big{(}\|C\|_{\infty}+\gamma+(1+\epsilon)e\Big{)}\epsilon.$

For ease of notation we denote
$\alpha=24\sqrt{N}\Big{(}\|C\|_{\infty}+\gamma+(1+\epsilon)e\Big{)}\epsilon$.
Combining these facts with 4.12 then yields

$\displaystyle\int_{S^{N-1}}B(\mathcal{B}^{e},u)d\sigma(u)$
$\displaystyle\leq\sum_{i=1}^{m}w_{i}B(\mathcal{B}^{e},u_{i})+\alpha$
$\displaystyle\leq V^{DP}+\gamma+(1+\epsilon)e+\alpha$ $\displaystyle\leq
V^{CP}+8\sqrt{N}\|C\|_{\infty}\epsilon+\gamma+(1+\epsilon)e+\alpha$
$\displaystyle\leq V^{CP}+\beta+\gamma,$

which implies $\mathcal{B}^{e}\in\mathcal{C}^{\gamma+\beta}$. ∎

##  5\. Numerical examples

Figure 1. We discretise the true outreach requirement (black circle) into only
nine directions (blue). This highlights the difference between
$\mathcal{B}^{*}$ from 4.2 (green) and $\mathcal{B}^{\prime}$ from Corollary
4.3 (orange). $\mathcal{B}^{*}$ always lies inside of $\mathcal{B}^{\prime}$.

######  Example 5.1 (Difference between $\mathcal{B}^{*}$ and
$\mathcal{B}^{\prime}$).

Figure 1 highlights the difference between the convex hull $\mathcal{B}^{*}$
from 4.2, and the intersection of half-spaces $\mathcal{B}^{\prime}$ from
Corollary 4.3. We use the unit circle outreach requirement $C=1$ and sample it
in nine evenly spaced directions. We see that the half-spaces defining
$\mathcal{B}^{\prime}$ each tangent the unit circle from the outside. On the
other hand, the corners defining $\mathcal{B}^{*}$ lie on the circle, giving a
convex hull inside the circle.

This means that using $\mathcal{B}^{\prime}$ will be a more conservative
estimate, and therefore a safer choice. In this particular case we even have
$\mathcal{B}^{\prime}\in\mathcal{C}^{\infty}$, making it a $(C,S^{N-1})$-valid
contour without the need for inflation as per 4.13.

Figure 2. Left: Periodic constraint function $C$ constructed such that
Equation 4.1 has several shapes with minimal perimeter. Right: The outreach
requirement boils down to requiring the shape to touch the four sides of a
square (blue). A specific numerical implementation of our method (7.3) output
the green shape. We highlight two other optimal shapes (orange).

######  Example 5.2 (Multiple optimal shapes).

We construct a Lipschitz-continuous outreach requirement (Figure 2, left)
which requires the shape to reach outreach 1 in each of the four cardinal
directions. For this requirement, there are infinitely many shapes with the
optimal perimeter. There are two distinct solution minimising the area: the
two diagonal line segments with zero area. However, interpolating the two
diagonal extremes are infinitely many 45 degree tilted rectangles, also with
optimal perimeter.

Figure 3. The naive method fails to output a convex shape satisfying the
requirements, when the outreach function $C$ contains noise. We highlight a
violated outreach constraint in blue. The plots are the same, with the right
one being zoomed in.

######  Example 5.3 (Comparing with naive method).

In [12], they compute $C$ under the assumption that the environmental loads,
$V$, are modeled as a sequence of i.i.d. random variables
$\\{W_{n}\\}_{n=0}^{\infty}$. Specifically, they assume that $V_{t}=W_{\lfloor
t/\Delta t\rfloor}$ for a time increment $\Delta t\in\mathbb{R}_{+}$, where
$\lfloor\cdot\rfloor$ denotes the floor function. They then define $C(u)$ by
the upper $p_{e}$-quantile of $\langle W,u\rangle$, for a target exceedance
probability $p_{e}$. This will guarantee that the mean time to failure for any
convex failure set not intersecting with a $(C,S^{N-1})$-valid contour is at
least $\Delta t/p_{e}$. We select $p_{e}={1}/{29200}$ and $\Delta t=3$ hours,
implying a 10 year lower bound on the mean time to failure.

The suggested method presented in the aforementioned article [12], as well as
the recommended practises of DNV [3], is the following. Find a model for $W$,
simulate a number of samples, and use the empirical quantiles of $\langle
W,u\rangle$ as an estimate of $C(u)$ for a finite selection of directions. We
choose $3\times 10^{5}$ samples in $360$ uniformly spaced directions.

In [12], $W$ was modelled as $W=(H,T)$. Here $H$ is a 3-parameter Weibull-
distributed random variable in $\mathbb{R}$ representing significant wave
height. $H$ has scale $2.259$, shape $1.285,$ and location $0.701$. Similarly,
$T$ represents the zero-upcrossing wave period and is assumed to follow a
conditional log-normal distribution, i.e. $\ln(T)$ is normally distributed
with with conditional mean $1.069+0.898H^{0.243},$ and conditional standard
deviation $0.025+0.263e^{-0.148H}.$

It is further suggested to construct $\mathcal{B}$ by

$\mathcal{B}=\bigcap_{u\in S^{N-1}}\Pi^{-}(u,C(u)).$ (5.1)

We will henceforth refer to (5.1) as the naive method.

The estimated $C$ is slightly noisy. As pointed out in e.g. [10, 6], this
noise may causes the naive method to fail to satisfy the outreach
requirements. For an explanation on why this occurs, we refer to either [10,
6] or the discussion around Figure 7.

As seen in Figure 3, the naive method outputs an improper contour. Using the
naive method with the $C$ from 5.2, would cause it to output the single point
$(0,0)$, which does not satisfy the outreach requirements.

Figure 4. Shape found by Equation 4.5 for the 3d example described in 5.4.

######  Example 5.4 (Three dimensions).

To demonstrate our method in three dimensions, we use an example from [20].
The construction of $C$ is similar to 5.3. The sequence $W=(H,T,U)$
distributed as follows. $H$ follows a 3-parameter Weibull distribution with
scale $1.798$, shape $1.214$ and location $0.856$. Given $H$, $\ln(T)$ is
normally distributed with mean $-1.010+2.847H^{0.075}$ and standard deviation
$0.161+0.146e^{-0.683H}$. Finally, given $H$, $U$ follows a 2-parameter
Weibull distribution with scale $2.58+0.12H^{1.6}$ and shape $4.6+2.05H$. We
use the empirical quantiles with $10^{6}$ samples of $\langle W,u\rangle$ to
estimate $C(u)$, and select $p_{e}=\frac{1}{29200}$.

For discretization, we sample $C$ according to the cubed hypersphere
quadrature with 10 subdivisions (8.1). Then we solve Equation 4.5 and compute
the convex hull $\mathcal{B}^{*}$ defined in 4.2. Figure 4 visualizes the
resulting contour.

Figure 5. Left: A 3-Lipschitz continuous constraint function $C$. Right: The
empirical convergence rate of our method matches the rate $O(1/m)$ given by
our theory (4.13).

######  Example 5.5 (Empirical convergence rate).

Figure 5 demonstrates the empirical convergence rate of our method on a
3-Lipschitz function consisting of three spikes. The optimal shape, i.e. the
sole element of $\mathcal{C}^{0}$, is an equilateral triangle. Since $C$ is
only sampled in a finite number of directions, and these directions rarely
exactly match the spikes of $C$, the samples underestimate $C$. This leads the
direct (not inflated) discrete solution $\mathcal{B}^{\prime}$ to violate the
constraint (4.2) in unseen directions. We plot the largest such constraint
violation, i.e., $\sup_{u\in S^{1}}C(u)-B(\mathcal{B}^{\prime},u)$, and see
that it is indeed bounded as per 4.13, which guarantees convergence of order
$O(1/m)$. The perimeter difference between the solution $\mathcal{B}^{\prime}$
found by our method and the optimal solution $\mathcal{B}^{*}$, i.e.,

$2\pi\left|\int_{S^{1}}B(\mathcal{B}^{\prime},u)d\sigma(u)-\int_{S^{1}}B(\mathcal{B}^{*},u)d\sigma(u)\right|,$

also converges like $O(1/m)$ as predicted by the bound from 4.13.

Figure 6. Left: A outreach function corresponding to the outreach function of
an equilateral triangle. Right: The empirical convergence rate for this case
seems to be $O(1/m^{2})$.

######  Example 5.6 (Empirical convergence is often $O(1/m^{2})$).

While the convergence rate $O(1/m)$ can not be improved in general, as seen in
5.5, in practice, we often see the faster rate $O(1/m^{2})$. For example, we
may choose $C$ as the outreach function of an equilateral triangle, i.e.,

$C(u)=\max\\{\cos(\theta),\ \cos(\theta-2\pi/3),\ \cos(\theta-4\pi/3)\\},$

for $u=\left(\cos(\theta),\sin(\theta)\right)$. In this case, the solution
$\mathcal{B}^{\prime}$ found by our method always satisfies the continuous
constraints (4.2) perfectly, and we empirically find a convergence rate of
$O(1/m^{2})$. Note that while $C$ is $\sqrt{3}/2$-Lipschitz continuous, it is
not everywhere differentiable, and the optimal shape (equilateral triangle)
has sharp corners.

##  6\. Connection with Hausdorff Topology

While the previous section guarantees the construction of arbitrarily near-
optimal $(S^{N-1},C)$-valid contours, there is still the question of whether
all elements of $\mathcal{C}^{0}$ can be approximated in this way. In order to
examine this question, we will need the concept of the Hausdorff metric. The
resulting topology turns out to be a natural framework for examining
convergence of the discrete approximations of our continuous problem, but it
will also allow us to properly prove our earlier claim that the continuous
problem indeed has optimal solutions.

###  6.1. Basic Concepts and Definitions

The main tool we will use here is the Hausdorff metric, defined as follows.

######  Definition 6.1.

Let $(X,d)$ be a metric space, and let $F(X)$ denote the collection of all
non-empty, compact subsets of $X$. For any $x\in X$ and $A,\,B\in F(X)$, we
can define $d(x,B)=d(B,x)=\min_{b\in\mathcal{B}}d(x,b)$ and

$d_{\mathcal{H}}(A,B)=\max\left(\max_{a\in A}d(a,B),\,\max_{b\in
B}d(A,b)\right).$

The set-function $d_{\mathcal{H}}$ is referred to as the Hausdorff distance.

We have the following basic properties of $d_{\mathcal{H}}$, for a proof of
these properties we refer to [15].

######  Proposition 6.2.

The space $(F(X),d_{\mathcal{H}})$ is a metric space. Furthermore, if $(X,d)$
is a complete and compact metric space, then $(F(X),d_{\mathcal{H}})$ is
complete and compact as well. Lastly, if $X$ is a Banach space and
$\\{A_{n}\\}_{n=1}^{\infty}\subset F(X)$ is a sequence of convex sets
converging to some set $A\in F(X)$, then $A$ is also convex.

In what follows, we will consider $(\mathbb{R}^{N},d)$ where $d$ is the
canonical Euclidean metric on $\mathbb{R}^{N}$. This allows us to define the
Hausdorff metric on $F(\mathbb{R}^{N})$, but also allows us to discuss
$F(F(\mathbb{R}^{N}))$, i.e. compact collections (in $d_{\mathcal{H}}$) of
compact subsets of $\mathbb{R}^{N}$ and the associated metric,
$d_{\mathcal{H}_{\mathcal{H}}}$. With these definitions we can discuss
$d_{\mathcal{H}_{\mathcal{H}}}(\mathcal{C}^{0},\mathcal{D}^{\gamma})$ which
quantifies how well our discrete problem can approximate the entirety of
$\mathcal{C}^{0}$.

###  6.2. Existence of Solutions to the Continuous Problem

Our first point of order is our previous claim of existence of solutions to
Equation 4.1.

######  Theorem 6.3.

Define the objective function
$\phi\colon\mathcal{C}^{\infty}\mapsto[V^{CP},\infty)$ by

$\phi(\mathcal{B})=\int_{S^{N-1}}B(\mathcal{B},u)d\sigma(u).$

We then have that $\phi$ is Lipschitz continuous in
$(F(\mathbb{R}^{N}),d_{\mathcal{H}})$ with Lipschitz constant $1$.
Furthermore, for any $\gamma\geq 0$, $\mathcal{C}^{\gamma}\subset
F(\mathbb{R}^{N})$ is non-empty and compact in the resulting Hausdorff
topology. As a specific consequence of this, the continuous problem (4.1) has
at least one optimal solution.

###### Proof.

In what follows, we will need the following relation. If
$\mathcal{B}_{1},\,\mathcal{B}_{2}\subset\mathbb{R}^{N}$ are compact then
$|B(\mathcal{B}_{1},u)-B(\mathcal{B}_{2},u)|\leq
d_{\mathcal{H}}(\mathcal{B}_{1},\mathcal{B}_{2})$ for all $u\in S^{N-1}$. To
see this, we pick $p_{1}\in\mathcal{B}_{1}$ such that $\langle
p_{1},u\rangle=B(\mathcal{B}_{1},u)$. From the definition of the Hausdorff
distance, there must be some $p_{2}\in\mathcal{B}_{2}$ such that
$\|p_{1}-p_{2}\|\leq d_{\mathcal{H}}(\mathcal{B}_{1},\mathcal{B}_{2})$ which
yields

$\displaystyle B(\mathcal{B}_{1},u)$ $\displaystyle=\langle p_{1},u\rangle$
$\displaystyle=\langle p_{1}-p_{2},u\rangle+\langle p_{2},u\rangle$
$\displaystyle\leq
d_{\mathcal{H}}(\mathcal{B}_{1},\mathcal{B}_{2})+B(\mathcal{B}_{2},u).$

This proves that $B(\mathcal{B}_{1},u)-B(\mathcal{B}_{2},u)\leq
d_{\mathcal{H}}(\mathcal{B}_{1},\mathcal{B}_{2})$, and an identical argument
with $B_{1}$ and $B_{2}$ interchanged gives
$B(\mathcal{B}_{2},u)-B(\mathcal{B}_{1},u)\leq
d_{\mathcal{H}}(\mathcal{B}_{1},\mathcal{B}_{2})$. This implies that for any
$u\in S^{N-1}$, the function $\mathcal{B}\mapsto B(\mathcal{B},u)$ is
Lipschitz continuous with Lipschitz constant $1$.

Next, we fix some $\gamma\geq 0$ and aim to prove compactness of
$\mathcal{C}^{\gamma}$, leaving non-emptiness for later. Note that
$\mathcal{C}^{\gamma}$ is either non-empty or trivially compact, as such we
can, without loss of generality, assume that $\mathcal{C}^{\gamma}$ is non-
empty. Furthermore, by Corollary 4.11, we note that for every
$\mathcal{B}\in\mathcal{C}^{\gamma}$ we have $\mathcal{B}\subset K_{\gamma}$
where

$K_{\gamma}=\\{x\in\mathbb{R}^{N}:\|x\|\leq
4\sqrt{N}(\|C\|_{\infty}+\gamma)\\}.$

If we denote by $F(K_{\gamma})$ the collection of all compact subsets of
$K_{\gamma}$, we have that $\mathcal{C}^{\gamma}\subset F(K_{\gamma})$.
Furthermore, by 6.2, we have that $F(K_{\gamma})\subset F(\mathbb{R}^{N})$
equipped with the Hausdorff metric is a complete and compact metric space.

We next aim to prove that $\mathcal{C}^{\gamma}$ is a closed (and therefore
compact) subset of $F(K_{\gamma})$ in the Hausdorff topology. To see this,
consider any convergent sequence
$\\{B_{n}\\}_{n=1}^{\infty}\subset\mathcal{C}^{\gamma}\subset F(K_{\gamma})$
with $\mathcal{B}_{n}\to\mathcal{B}$. By 6.2 we have that $\mathcal{B}$ is
convex, and by completeness of $F(K_{\gamma})$ we have $\mathcal{B}$ compact.
Furthermore, by continuity of $\mathcal{B}\mapsto B(\mathcal{B},u)$, we have
for any $u\in S^{N-1}$ that

$B(\mathcal{B},u)=\lim_{n\to\infty}B(\mathcal{B}_{n},u)\geq C(u),$

implying $\mathcal{B}\in\mathcal{C}^{\infty}$. Lastly, by
$B(\mathcal{B}_{n},u)\leq\max_{p\in\mathcal{B}_{n}}\|p\|\leq
4\sqrt{N}(\|C\|_{\infty}+\gamma)$ for all $u\in S^{N-1}$, we can apply the
dominated convergence theorem to get

$\displaystyle\int_{S^{N-1}}B(\mathcal{B},u)d\sigma(u)$
$\displaystyle=\int_{S^{N-1}}\lim_{n\to\infty}B(\mathcal{B}_{n},u)d\sigma(u)$
$\displaystyle=\lim_{n\to\infty}\int_{S^{N-1}}B(\mathcal{B}_{n},u)d\sigma(u)$
$\displaystyle\leq V^{CP}+\gamma,$

which implies $\mathcal{B}\in\mathcal{C}^{\gamma}$. As a consequence, for any
$\gamma\geq 0$, $\mathcal{C}^{\gamma}$ is a closed subset of the compact space
$F(K_{\gamma})$, and therefore itself compact.

As for non-emptiness of $\mathcal{C}^{\gamma}$ we first remark that
$\mathcal{C}^{\gamma}$ is non-empty for any $\gamma>0$. To see this, note by
the definition of $V^{CP}$ that there exists either an optimal solution in
$\mathcal{C}^{0}$ with mean width $V^{CP}$ or a sequence of near-optimal
solutions with mean width converging to $V^{CP}$. Either way, this implies
that $\mathcal{C}^{\gamma}$ is non-empty for any $\gamma>0$.

Next, assume $\gamma>0$ and note that for any
$\mathcal{B}_{1},\,\mathcal{B}_{2}\in\mathcal{C}^{\gamma}$ we have

$\displaystyle|\phi(\mathcal{B}_{1})-\phi(\mathcal{B}_{2})|$
$\displaystyle=\left|\int_{S^{N-1}}(B(\mathcal{B}_{1},u)-B(\mathcal{B}_{2},u))d\sigma(u)\right|$
$\displaystyle\leq\int_{S^{N-1}}\left|B(\mathcal{B}_{1},u)-B(\mathcal{B}_{2},u)\right|d\sigma(u)$
$\displaystyle\leq\int_{S^{N-1}}d_{\mathcal{H}}(\mathcal{B}_{1},\mathcal{B}_{2})d\sigma(u)$
$\displaystyle=d_{\mathcal{H}}(\mathcal{B}_{1},\mathcal{B}_{2}).$

This means that $\phi$ is Lipschitz, so it must attain a minimal value on
$\mathcal{C}^{\gamma}$ for any $\gamma>0$. This minimum, by definition, will
also be a minimum on $\mathcal{C}^{\infty}$. Consequently, this minimal point,
$\mathcal{B}_{\text{min}}$, must satisfy
$\phi(\mathcal{B}_{\text{min}})=V^{CP}$, yielding $\mathcal{C}^{0}$ non-empty.
∎

###  6.3. Convergence in Hausdorff Metric

With existence of solutions settled, along with some useful properties of
$\phi$ and $\mathcal{C}^{\gamma}$, we can move on to our main goal of this
section: To prove that we can arbitrarily well approximate the entirety of
$\mathcal{C}^{0}$ by $\mathcal{D}^{0}$ or $\mathcal{D}^{\gamma}$. To do so we
will consider

$d_{\mathcal{H}_{\mathcal{H}}}(\mathcal{C}^{0},\mathcal{D}^{\gamma})=\max\left(\max_{\mathcal{B}^{\prime}\in\mathcal{C}^{0}}\min_{\mathcal{B}\in\mathcal{D}^{\gamma}}d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{\prime}),\max_{\mathcal{B}^{\prime}\in\mathcal{D}^{\gamma}}\min_{\mathcal{B}\in\mathcal{C}^{0}}d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{\prime})\right).$
(6.1)

The primary goal of this section is to show that for a sequence of
quadratures, $\\{(\mathcal{S}_{n},W_{n})\\}_{i=1}^{\infty}$, we have
$\\{\gamma_{n}\\}_{i=1}^{\infty}$, with $\gamma_{n}\to 0$ such that
$d_{\mathcal{H}_{\mathcal{H}}}(\mathcal{C}^{0},\mathcal{D}^{\gamma_{n}}(\mathcal{S}_{n},W_{n}))\to
0$. This would imply that for any given
$\mathcal{B}^{\prime}\in\mathcal{C}^{0}$ there is some set
$\mathcal{B}\in\mathcal{D}^{\gamma_{n}}(\mathcal{S}_{n},W_{n})$ that
approximates it, meaning that all optimal solutions can be approximated by our
discrete solutions. Conversely, for any
$\mathcal{B}\in\mathcal{D}^{\gamma_{n}}(\mathcal{S}_{n},W_{n})$, we know it
will be close to some $\mathcal{B}\in\mathcal{C}^{0}$ in Hausdorff distance,
implying that our discrete solutions will get closer and closer to our
continuous solutions.

It turns out that if we are only interested in guaranteeing that our discrete
solutions are close to a continuous solution we can drop the inclusion of
$\gamma_{n}$. In particular we will have
$\max_{\mathcal{B}^{\prime}\in\mathcal{D}^{0}(\mathcal{S}_{n},W_{n})}\min_{\mathcal{B}\in\mathcal{C}^{0}}d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{\prime})\to
0.$ Furthermore, if the continuous problem (4.1) has a unique solution, then
$d_{\mathcal{H}_{\mathcal{H}}}(\mathcal{C}^{0},\mathcal{D}^{0}(\mathcal{S}_{n},W_{n}))\to
0$.

However, in order to even consider this distance we will first need to
guarantee that $\mathcal{D}^{\gamma}$ is a compact set in the Hausdorff
metric.

######  Corollary 6.4.

Assume that $\\{(u_{i},w_{i})\\}_{i=1}^{m}\subset\mathcal{S}\times[0,\infty)$
is an $\epsilon$-accurate quadrature with
$\delta\coloneqq\mathrm{disp}(\mathcal{S})$ satisfying
$\epsilon,\delta\leq\frac{1}{10\sqrt{N}}$. We then have that
$\mathcal{D}^{\gamma}$ is compact in $d_{\mathcal{H}}$.

###### Proof.

We first note that Lemma 4.10 yields $\mathcal{D}^{\gamma}\subset
F(K_{\gamma}^{\prime})$ for

$K_{\gamma}^{\prime}=\\{x\in\mathbb{R}^{N}:\|x\|\leq
12\sqrt{N}(\|C\|_{\infty}+\gamma)\\}.$

By defining

$\psi(\mathcal{B})=\sum_{i=1}^{m}w_{i}B(\mathcal{B},u_{i}),$

we can then repeat the arguments of 6.3 with $K_{\gamma}^{\prime},\psi$
replacing $K_{\gamma},\phi$, which proves the desired result. ∎

With this established we know that (6.1) is well defined, and what remains is
finding ways to bound it. We remark that
$\max_{\mathcal{B}^{\prime}\in\mathcal{C}^{0}}\min_{\mathcal{B}\in\mathcal{D}^{\gamma}}d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{\prime})$
in (6.1) can be bounded by considering the triangular inequality

$d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{\prime})\leq
d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{e})+d_{\mathcal{H}}(\mathcal{B}^{e},\mathcal{B}^{\prime}),$
(6.2)

where $\mathcal{B}^{e}=\bigcap_{v\in
S^{N-1}}\Pi^{-}\left(v,B(\mathcal{B},v)+e\right)$ for some appropriate $e$.

The first term of the right side is easily dealt with by extending the results
of Lemma 4.7 to the setting of $d_{\mathcal{H}}$.

######  Lemma 6.5.

Let $\mathcal{B}$ be a convex and compact set and define

$\mathcal{B}^{e}=\bigcap_{v\in
S^{N-1}}\Pi^{-}\left(v,B(\mathcal{B},v)+e\right).$

We then have that $d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{e})=e$.

###### Proof.

Consider the alternative construction

$\widehat{\mathcal{B}}=\\{x\in\mathbb{R}^{N}:d(x,\mathcal{B})\leq e\\}.$

We immediately see that $\widehat{\mathcal{B}}$ is a compact convex set
satisfying $d_{\mathcal{H}}(\mathcal{B},\widehat{\mathcal{B}})=e$, so all we
need is to show $\mathcal{B}^{e}=\widehat{\mathcal{B}}$.

To prove this, we note that for all $x\in\widehat{\mathcal{B}}$ we can
decompose $x=b+c$ where $b\in\mathcal{B}$ and $\|c\|\leq e$. Conversely, if
$b\in\mathcal{B}$ and $\|c\|\leq e$ we have $b+c\in\widehat{\mathcal{B}}$.
Using this we get, for any $u\in S^{N-1}$, that

$\displaystyle B(\widehat{\mathcal{B}},u)$ $\displaystyle=\max\\{\langle
x,u\rangle:x\in\widehat{\mathcal{B}}\\}$ $\displaystyle=\max\\{\langle
b,u\rangle+\langle c,u\rangle:b\in\mathcal{B},\,\|c\|\leq e\\}$
$\displaystyle=B(\mathcal{B},u)+e.$

We may also recall from lemma 4.7 that
$B(\mathcal{B}^{e},u)=B(\mathcal{B},u)+e=B(\widehat{\mathcal{B}},u)$, for all
$u\in S^{N-1}$. This implies that $\mathcal{B}^{e}=\widehat{\mathcal{B}}$ by
3.5, which guarantees uniqueness of representation by $B$.

∎

The second term of the right side of (6.2) requires two steps to control. By
4.12, we can bound the mean width of $\mathcal{B}^{e}$ by the following
result. This result is almost identical to 4.13. In that result, however, we
consider the set $\mathcal{B}^{e}$ to be an inflation of $\mathcal{B}$ only in
directions $u\in\mathcal{S}$. In the following result we consider an inflation
of $\mathcal{B}$ in all directions $u\in S^{N-1}$.

######  Proposition 6.6.

Fix some $\epsilon$-accurate quadrature $\\{(u_{i},w_{i})\\}_{i=1}^{m}$ and
assume that $\mathcal{S}=\\{u_{i}\\}_{i=1}^{m}$ with
$\delta=\mathrm{disp}(\mathcal{S})$ satisfies
$\epsilon,\delta\leq\frac{1}{10\sqrt{N}}$. Let
$e=\delta\big{(}L_{C}+12\sqrt{N}(\|C\|_{\infty}+\gamma)\big{)}$ and define
$\mathcal{B}^{e}=\bigcap_{u\in
S^{N-1}}\Pi^{-}\left(u,B(\mathcal{B},u)+e)\right)$ for some
$\mathcal{B}\in\mathcal{D}^{\infty}$. Note here that we consider $u\in
S^{N-1}$ and not $u\in\mathcal{S}$ as in 4.13.

Then, for any $\mathcal{B}\in\mathcal{D}^{\gamma}$, $\gamma\geq 0$, we have
that

$\mathcal{B}^{e}\in\mathcal{C}^{\gamma+\beta},$

where $\beta=e+32\sqrt{N}(\|C\|_{\infty}+\gamma)\,\epsilon$.

###### Proof.

We know from Lemmas 4.6, 4.7 and 4.10 that $\mathcal{B}^{e}$ satisfies

$\displaystyle B(\mathcal{B}^{e},u)$
$\displaystyle=B(\mathcal{B},u)+\delta(L_{C}+12\sqrt{N}(\|C\|_{\infty}+\gamma))$
$\displaystyle\geq\Big{(}C(u)-e\Big{)}+\delta(L_{C}+12\sqrt{N}(\|C\|_{\infty}+\gamma))$
$\displaystyle=C(u)$

for all $u\in S^{N-1}$, which implies
$\mathcal{B}^{e}\in\mathcal{C}^{\infty}$. Furthermore, we have by the
definition of $\epsilon$-accurate quadratures, 3.3 and Lemma 4.10 that

$\left|\sum_{i=1}^{m}w_{i}B(\mathcal{B},u_{i})-\int_{S^{N-1}}B(\mathcal{B},u)d\sigma(u)\right|\leq
24\sqrt{N}(\|C\|_{\infty}+\gamma)\epsilon.$

Combining these facts with 4.12 then yields

$\displaystyle\int_{S^{N-1}}B(\mathcal{B}^{e},u)d\sigma(u)$
$\displaystyle=\int_{S^{N-1}}B(\mathcal{B},u)d\sigma(u)+e$
$\displaystyle\leq\sum_{i=1}^{m}w_{i}B(\mathcal{B},u_{i})+24\sqrt{N}(\|C\|_{\infty}+\gamma)\epsilon+e$
$\displaystyle\leq V^{DP}+\gamma+24\sqrt{N}(\|C\|_{\infty}+\gamma)\epsilon+e$
$\displaystyle\leq
V^{CP}+8\sqrt{N}\|C\|_{\infty}\epsilon+\gamma+24\sqrt{N}(\|C\|_{\infty}+\gamma)\epsilon+e$
$\displaystyle\leq V^{CP}+\gamma+\beta,$

which implies $\mathcal{B}^{e}\in\mathcal{C}^{\gamma+\beta}$. ∎

With this result, for any $\mathcal{B}^{\prime}\in\mathcal{C}^{0}$ and
$\mathcal{B}^{e}$ defined as in 6.6, we have
$d_{\mathcal{H}}(\mathcal{B}^{\prime},\mathcal{B}^{e})\leq
d_{\mathcal{H}_{\mathcal{H}}}(\mathcal{C}^{\gamma},\mathcal{C}^{0})$. This can
be controlled by the following.

######  Proposition 6.7.

Consider the Hausdorff metric on the set $F(\mathcal{C}^{\infty})$, i.e. the
set of all compact subsets of $\mathcal{C}^{\infty}$ where
$\mathcal{C}^{\infty}$ itself is also equipped with a Hausdorff metric. We
then have that

$\lim_{\gamma\to
0}d_{\mathcal{H}_{\mathcal{H}}}(\mathcal{C}^{\gamma},\mathcal{C}^{0})=0.$

###### Proof.

We first recall from 6.3 that $\mathcal{C}^{\gamma}$ is compact and that
$\phi:\mathcal{C}^{\infty}\to[V^{CP},\infty)$ defined by
$\phi(\mathcal{B})=\int_{S^{N-1}}B(\mathcal{B},u)d\sigma(u)$ is a Lipschitz
continuous function with Lipschitz constant $1$. Also, note that since
$\mathcal{C}^{0}\subset\mathcal{C}^{\gamma}$, we have

$d_{\mathcal{H}_{\mathcal{H}}}(\mathcal{C}^{\gamma},\mathcal{C}^{0})=\max_{\mathcal{B}\in\mathcal{C}^{\gamma}}\min_{\mathcal{B}^{\prime}\in\mathcal{C}^{0}}d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{\prime}).$

Next, pick some $\gamma,\beta>0$. Since $\mathcal{C}^{\gamma}$ is compact, we
can consider a finite open covering $\\{\mathcal{U}_{i}\\}_{i=1}^{I}$ such
that $\mathrm{diam}(\mathcal{U}_{i})\leq\beta$ for all $i=1,\dots,I$. Note
that by Lipschitz continuity of $\phi$, we have for all $i=1,\dots,I$ that
$\phi(\mathcal{B})\leq\gamma+\beta$ for any $\mathcal{B}\in\mathcal{U}_{i}$.
As a consequence, if we then define $\overline{\mathcal{U}_{i}}$ as the
closure of $\mathcal{U}_{i}$ in the Hausdorff metric, we know for all
$i=1,\dots,I$, that $\overline{\mathcal{U}_{i}}$ must be a closed subset of
the compact set $\mathcal{C}^{\gamma+\beta}$, which implies that
$\overline{\mathcal{U}_{i}}$ is compact as well.

This implies that $\phi$ must attain a minimum on $\overline{\mathcal{U}}_{i}$
which lets us define $\\{\psi_{i}\\}_{i=1}^{I}$ by
$\psi_{i}=\min_{\mathcal{B}\in\mathcal{U}_{i}}\phi(\mathcal{B})$. We then
separate the sets that overlap with $\mathcal{C}^{0}$ by defining
$\mathcal{I}=\\{i=1,\dots,I:\psi_{i}=V^{CP}\\}$ and
$\mathcal{J}=\\{i=1,\dots,I:\psi_{i}>V^{CP}\\}$. If we then define
$\psi_{min}=\min_{j\in\mathcal{J}}\psi_{j}>V^{CP}$, we can pick some
$\alpha\in\big{(}0,\min(\gamma,\psi_{\min}-V^{CP})\big{)}$ which implies that
$\phi(\mathcal{B})\geq\psi_{min}>V^{CP}+\alpha$ for any
$\mathcal{B}\in\cup_{j\in\mathcal{J}}\overline{\mathcal{U}}_{j}$. As a
consequence, we have

$\bigcup_{j\in\mathcal{J}}\overline{\mathcal{U}}_{j}\cap\mathcal{C}^{\alpha}=\emptyset.$

However, since $\\{\mathcal{U}_{i}\\}_{i=1}^{I}$ is a covering of
$\mathcal{C}^{\gamma}\supset\mathcal{C}^{\alpha}$ we must have that

$\mathcal{C}^{\alpha}\subseteq\bigcup_{i\in\mathcal{I}}\overline{\mathcal{U}}_{i}.$

This implies that for every $\mathcal{B}\in\mathcal{C}^{\alpha}$ we have
$\mathcal{B}\in\overline{\mathcal{U}}_{i^{\prime}}$ for some
$i^{\prime}\in\mathcal{I}$. Since $\psi_{i^{\prime}}=V^{CP}$, there is some
$\mathcal{B}^{\prime}\in\overline{\mathcal{U}}_{i^{\prime}}$ such that
$\phi(\mathcal{B}^{\prime})=V^{CP}$ which implies
$\mathcal{B}^{\prime}\in\mathcal{C}^{0}$. By
$\mathrm{diam}(\overline{\mathcal{U}}_{i})=\mathrm{diam}(\mathcal{U}_{i})\leq\beta$
we then finally get that
$d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{\prime})\leq\beta$, but since
$\mathcal{B}$ was arbitrary we also have
$d_{\mathcal{H}_{\mathcal{H}}}(\mathcal{C}^{0},\mathcal{C}^{\alpha})\leq\beta$.

In summary, we see that for every $\beta>0$ there exists some $\alpha>0$ such
that
$d_{\mathcal{H}_{\mathcal{H}}}(\mathcal{C}^{0},\mathcal{C}^{\alpha})\leq\beta$,
which implies $\lim_{\gamma\to
0}d_{\mathcal{H}_{\mathcal{H}}}(\mathcal{C}^{0},\mathcal{C}^{\gamma})=0$ by
monotonicity.

∎

It turns out that the triangle inequality of (6.2) is not sufficient to
control (6.1). In particular, we also need to handle
$\max_{\mathcal{B}^{\prime}\in\mathcal{D}^{\gamma}}\min_{\mathcal{B}\in\mathcal{C}^{0}}d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{\prime})$,
which equals 0 if $\mathcal{C}^{0}\subset\mathcal{D}^{\gamma}$. Fortunately, a
$\gamma$ such that this is satisfied can be attained.

######  Lemma 6.8.

Fix some $\epsilon$-accurate quadrature $\\{(u_{i},w_{i})\\}_{i=1}^{m}$ and
assume that $\mathcal{S}=\\{u_{i}\\}_{i=1}^{m}$ with
$\delta=\mathrm{disp}(\mathcal{S})$ satisfies
$\epsilon,\delta\leq\frac{1}{10\sqrt{N}}$.

Then $\mathcal{C}^{0}\subset\mathcal{D}^{\gamma}$ for
$\gamma=16\sqrt{N}\|C\|_{\infty}(2\epsilon+\delta)+L_{C}\delta$.

###### Proof.

Take any $\mathcal{B}\in\mathcal{C}^{0}$, we then have, for all
$u\in\mathcal{S}$, that $B(\mathcal{B},u)\geq C(u)$, which implies
$\mathcal{B}\in\mathcal{D}^{\infty}$. Furthermore, 3.3 and Corollary 4.11 give
us

$\left|V^{CP}-\sum_{i=1}^{m}w_{i}B(\mathcal{B},u_{i})\right|\leq
8\sqrt{N}\|C\|_{\infty}\epsilon.$

Combining these facts with 4.12 yields

$\displaystyle\sum_{i=1}^{m}w_{i}B(\mathcal{B},u_{i})$ $\displaystyle\leq
V^{CP}+8\sqrt{N}\|C\|_{\infty}\epsilon$ $\displaystyle\leq
V^{DP}+12\sqrt{N}\|C\|_{\infty}(2\epsilon+\delta)+L_{C}\delta+8\sqrt{N}\|C\|_{\infty}\epsilon$
$\displaystyle\leq V^{DP}+\gamma,$

which implies $\mathcal{B}\in\mathcal{D}^{\gamma}$. ∎

With all our technical results, we are ready to prove the second main result
of this section.

######  Theorem 6.9.

Consider a sequence, $\\{(\mathcal{S}_{n},W_{n})\\}_{i=1}^{\infty}$, with
$\mathcal{S}_{n}=(u_{i}^{n})_{i=1}^{I_{n}}$ and
$W_{n}=(w_{i}^{n})_{i=1}^{I_{n}}$ such that
$\\{(u_{i}^{n},w_{i}^{n})\\}_{i=1}^{I_{n}}\subset\mathcal{S}_{n}\times W_{n}$
forms an $\epsilon_{n}$-accurate quadrature. Further assume that
$\epsilon_{n}$ and $\delta_{n}=\mathrm{disp}(\mathcal{S}_{n})$ both converge
to 0 and satisfy $\epsilon_{n},\delta_{n}\leq\frac{1}{10\sqrt{N}}$ for all
$n\in\mathbb{N}^{+}$. For ease of notation, we will denote
$\mathcal{D}^{\gamma}(\mathcal{S}_{n},W_{n})$ by $\mathcal{D}^{\gamma}_{n}$
for any $\gamma\geq 0$.

If we define

$\gamma_{n}=16\sqrt{N}\|C\|_{\infty}(2\epsilon_{n}+\delta_{n})+L_{C}\delta_{n},$

we then have that

$\lim_{n\to\infty}d_{\mathcal{H}_{\mathcal{H}}}\Big{(}\mathcal{D}^{\gamma_{n}}_{n},\mathcal{C}^{0}\Big{)}=0,$

and

$\lim_{n\to\infty}\max_{\mathcal{B}\in\mathcal{D}^{0}_{n}}\min_{\mathcal{B}^{\prime}\in\mathcal{C}^{0}}d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{\prime})=0.$

Furthermore, if there is a unique optimal solution to the continuous problem,
i.e. $\mathcal{C}^{0}=\\{\mathcal{B}^{\text{CP}}\\}$ for some
$\mathcal{B}^{\text{CP}}\subset\mathbb{R}^{N}$, we have

$\lim_{n\to\infty}d_{\mathcal{H}_{\mathcal{H}}}\Big{(}\mathcal{D}^{0}_{n},\mathcal{C}^{0}\Big{)}=0.$

###### Proof.

We first note that Lemma 6.8 implies
$\mathcal{C}^{0}\subset\mathcal{D}^{\gamma_{n}}_{n}$, which yields

$d_{\mathcal{H}_{\mathcal{H}}}\Big{(}\mathcal{D}^{\gamma_{n}}_{n},\mathcal{C}^{0}\Big{)}=\max_{\mathcal{B}\in\mathcal{D}^{\gamma_{n}}_{n}}\min_{\mathcal{B}^{\prime}\in\mathcal{C}^{0}}d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{\prime}).$

Consider therefore any $\mathcal{B}\in\mathcal{D}^{\gamma_{n}}_{n}$. From
Lemmas 4.6, 4.10 and 6.5 along with 6.6, we get that if we define
$\mathcal{B}^{e_{n}}$ by

$\mathcal{B}^{e_{n}}=\bigcap_{v\in
S^{N-1}}\Pi^{-}\left(v,B(\mathcal{B},v)+e_{n}\right),$

where $e_{n}=\delta_{n}(L_{C}+12\sqrt{N}(\|C\|_{\infty}+\gamma_{n}))$, we have
that $d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{e_{n}})=e_{n}$ and that
$\mathcal{B}^{e_{n}}\in\mathcal{C}^{\gamma_{n}+\beta_{n}}$ for

$\beta_{n}=32\sqrt{N}(\|C\|_{\infty}+\gamma_{n})\epsilon_{n}+e_{n}.$

As a consequence, we have by the triangle inequality that

$\displaystyle\min_{\mathcal{B}^{\prime}\in\mathcal{C}^{0}}d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{\prime})$
$\displaystyle\leq\min_{\mathcal{B}^{\prime}\in\mathcal{C}^{0}}d_{\mathcal{H}}(\mathcal{B}^{e_{n}},\mathcal{B}^{\prime})+d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{e_{n}})$
$\displaystyle\leq\max_{\mathcal{B}^{\prime\prime}\in\mathcal{C}^{\gamma_{n}+\beta_{n}}}\min_{\mathcal{B}^{\prime}\in\mathcal{C}^{0}}d_{\mathcal{H}}(\mathcal{B}^{\prime\prime},\mathcal{B}^{\prime})+e_{n}$
$\displaystyle=d_{\mathcal{H}}(\mathcal{C}^{\gamma_{n}+\beta_{n}},\mathcal{C}^{0})+e_{n}.$

By noting that $\lim_{n\to\infty}\gamma_{n}+\beta_{n}=0$, we have
$d_{\mathcal{H}_{\mathcal{H}}}(\mathcal{C}^{\gamma_{n}+\beta_{n}},\mathcal{C}^{0})\to
0$ by 6.7. This further yields

$\max_{\mathcal{B}\in\mathcal{D}_{n}^{\gamma_{n}}}\min_{\mathcal{B}^{\prime}\in\mathcal{C}^{0}}d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{\prime})\to
0,$

which yields the first part of the proof. Furthermore, the second equation
follows from

$\displaystyle\max_{\mathcal{B}\in\mathcal{D}^{0}_{n}}\min_{\mathcal{B}^{\prime}\in\mathcal{C}^{0}}d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{\prime})$
$\displaystyle\leq\max_{\mathcal{B}\in\mathcal{D}^{\gamma_{n}}_{n}}\min_{\mathcal{B}^{\prime}\in\mathcal{C}^{0}}d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{\prime})\to
0$

Similarly, if $\mathcal{C}^{0}=\\{\mathcal{B}^{\text{CP}}\\}$,

$\displaystyle
d_{\mathcal{H}_{\mathcal{H}}}\left(\mathcal{D}^{0}_{n},\mathcal{C}^{0}\right)$
$\displaystyle=\max\left(\max_{\mathcal{B}\in\mathcal{D}^{0}_{n}}\min_{\mathcal{B}^{\prime}\in\mathcal{C}^{0}}d_{\mathcal{H}}\left(\mathcal{B},\mathcal{B}^{\prime}\right),\max_{\mathcal{B}^{\prime}\in\mathcal{C}^{0}}\min_{\mathcal{B}\in\mathcal{D}^{0}_{n}}d_{\mathcal{H}}\left(\mathcal{B},\mathcal{B}^{\prime}\right)\right)$
$\displaystyle=\max\left(\max_{\mathcal{B}\in\mathcal{D}^{0}_{n}}d_{\mathcal{H}}\left(\mathcal{B},\mathcal{B}^{\text{CP}}\right),\min_{\mathcal{B}\in\mathcal{D}^{0}_{n}}d_{\mathcal{H}}\left(\mathcal{B},\mathcal{B}^{\text{CP}}\right)\right)$
$\displaystyle=\max_{\mathcal{B}\in\mathcal{D}^{0}_{n}}d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{\text{CP}})$
$\displaystyle=\max_{\mathcal{B}\in\mathcal{D}^{0}_{n}}\min_{\mathcal{B}^{\prime}\in\mathcal{C}^{0}}d_{\mathcal{H}}(\mathcal{B},\mathcal{B}^{\prime})\to
0,$

which completes the proof. ∎

This theorem tells us that the optimal solution space of the continuous
problem can be effectively approximated by a near-optimal solution space of a
linear program. Furthermore, if the continuous solution is unique, then the
optimal discrete solution space is sufficient to approximate this solution.
Lastly, 6.9 also proves that all optimal solutions of our discrete problem can
be made arbitrarily close to a continuous one in terms of Hausdorff distance.
This complements 4.12, and provides an alternate perspective on how our
discrete problem approximates the continuous optimal solutions.

##  7\. Minimal Valid Contours in 2-D

In the linear program (4.5), we have several constraints in place to ensure
that the output corresponds to a convex set. In two dimensions, however, there
is a more efficient way of phrasing this property. This relates to the
presence of loops in the contour as discussed in e.g. [10].

To discuss this, we consider a finite
$\mathcal{S}=\\{u_{i}\\}_{i=1}^{m}\subset S^{1}$ and parameterise any
$u\in\mathcal{S}$ by the unique angle $\theta(u)\in[0,2\pi)$ such that
$u=(\cos(\theta),\sin(\theta))$. Using this parameterisation, we will consider
$\mathcal{S}$ to be an ordered set $\mathcal{S}=(u_{i})_{i=1}^{m}$ such that
$\theta(u_{i})<\theta(u_{i+1})$. Finally, we also denote $u_{m+1}=u_{1}$,
$u_{0}=u_{m}$, and $\theta_{i}=\theta(u_{i})$ for any $0\leq i\leq m+1$.

In (4.5) we have defined our constraints to ensure the
$B_{i}=B(\mathcal{B},u_{i})$ for some convex $\mathcal{B}$, to rephrase those
constraints for $N=2$ we define

$\mathcal{B}=\bigcap_{i=1}^{m}\Pi^{-}\left(u_{i},B_{i}\right),$ (7.1)

and examine when $B(\mathcal{B},u_{i})=B_{i}$ holds. To do so we will denote
the hyperplane $\Pi_{j}=\Pi(u_{j},B_{j})$ and the crossing point
$X_{j}=\Pi_{j}\cap\Pi_{j-1}$ for all $j$.

We see from Figure 7(a) that when $B(\mathcal{B},u_{i})=B_{i}$, the hyperplane
$\Pi_{i}$ supports $\mathcal{B}$. Furthermore, we can compute the length,
$L_{i}$ of the line segment $\mathcal{B}\cap\Pi_{i}$, which equals the
distance between $X_{i}$ and $X_{i-1}$, by

$\displaystyle L_{i}=$ $\displaystyle\frac{B_{i+1}-\langle
u_{i+1},u_{i}\rangle
B_{i}}{\sin(\theta_{i+1}-\theta_{i})}+\frac{B_{i-1}-\langle
u_{i-1},u_{i}\rangle B_{i}}{\sin(\theta_{i}-\theta_{i-1})}.$ (7.2)

The key observation comes from Figure 7(b), where the resulting contour
satisfies $B(\mathcal{B},u_{i})<B_{i}$, and as such we have
$\mathcal{B}\cap\Pi_{i}=\emptyset$. In particular, we note that $X_{i}$ and
$X_{i-1}$ switch sides. Since Equation 7.2 is based on projecting $X_{i}$ and
$X_{i-1}$ along $\Pi_{i}$, if we were to compute $L_{i}$ by (7.2), we would
see that while it still provides the distance between $X_{i}$ and $X_{i-1}$,
the sign of $L_{i}$ is now negative. This observation tells us that the
condition $B(\mathcal{B},u_{i})=B_{i}$, for all $i$, is equivalent to
$L_{i}\geq 0$ for all $i$.

$\mathcal{B}$$X_{i}$$X_{i-1}$$\Pi_{i+1}$$\Pi_{i}$$\Pi_{i-1}$ (a) Good Case:
$B(\mathcal{B},u_{i})=B_{i}$ and $L_{i}\geq 0$

$X_{i}$$X_{i-1}$$\Pi_{i+1}$$\Pi_{i}$$\Pi_{i-1}$$\mathcal{B}$ (b) Bad Case:
$B(\mathcal{B},u_{i})<B_{i}$ and $L_{i}<0$

Figure 7. Two cases for $\mathcal{B}$ (purple), defined by (7.1). The
condition $\mathcal{B}\cap\Pi_{i}\neq\emptyset$ fails based on the orientation
of $X_{i}$ and $X_{i-1}$ (red).

Using this equivalence we can restate our linear program for a quadrature,
$(\mathcal{S},W)$, as follows.

minimise $\displaystyle\sum_{i=1}^{m}w_{i}B_{i}$ (7.3) subject to
$\displaystyle L_{i}\geq 0$ $\displaystyle i=1,2,\dots,m$ $\displaystyle
B_{i}\geq C(u_{i})$ $\displaystyle i=1,2,\dots,m$ $\displaystyle u_{i}\in
S^{N-1}$ $\displaystyle i=1,2,\dots,m$ $\displaystyle
C(u_{i}),B_{i}\in\mathbb{R}$ $\displaystyle i=1,2,\dots,m$

Here, $L_{i}$ is defined as in (7.2). Furthermore, the restrictions $L_{i}\geq
0$ and $B_{i}\geq C(u_{i})$ for all $i$ imply that a $\mathcal{B}$ defined by
$\mathcal{B}=\bigcap_{i=1}^{m}\Pi^{-}\left(u_{i},B_{i}\right)$ must be a
convex set satisfying $B(\mathcal{B},u_{i})=B_{i}\geq C_{i}$. As such there
exists a collection of points $\\{p_{i}\\}_{i=1}^{m}\subset\mathcal{B}$ such
that $\langle p_{i},u_{i}\rangle\geq C_{i}$, implying that
$\left(\left(p_{i}\right)_{i=1}^{m},\,\left(B_{i}\right)_{i=1}^{m}\right)$ is
a feasible solution of our original linear problem (4.5). This, along with our
earlier discussion, shows that (7.3) is equivalent to (4.5), but phrased with
far less numerically demanding constraints.

However, due to no longer explicitly storing the points $(p_{i})_{i=1}^{m}$,
we are now limited in our explicit construction of sets. We can no longer
define
$\mathcal{B}^{*}=\operatorname{convh}\left(\left\\{p^{*}_{i}\right\\}_{i=1}^{m}\right)$
from 4.2 based on our linear program outputs, and as such exclusively rely on
$\mathcal{B}^{\prime}=\bigcap_{i=1}^{m}\Pi^{-}(u_{i},B_{i})$. This
construction, as mentioned in 4.5 and shown in 5.1, is more conservative and
therefore a safer choice than $\mathcal{B}^{*}$. As such we do not lose much
in considering this more efficient method.

Nevertheless, since $L_{i}$ represents the length of the $i$’th side this
restriction allows us to consider an alternative linear program where we
instead minimise $\sum_{i}L_{i}$, which equals the circumference of
$\mathcal{B}^{\prime}$. Optimising in mean width and circumference turns out
to be equivalent in the case where $\mathcal{S}$ is uniformly distributed and
$w_{i}=1/m$ for all $i$. When this is the case we have
$\theta_{i}-\theta_{i-1}=2\pi/m$ for all $i=2,3,\dots,m$ and
$2\pi+\theta_{1}-\theta_{m}=2\pi/m$, which yields

$\displaystyle\sum_{i=1}^{m}L_{i}$
$\displaystyle=\sum_{i=1}^{m}\frac{B_{i+1}-\langle u_{i+1},u_{i}\rangle
B_{i}}{\sin(\theta_{i+1}-\theta_{i})}+\frac{B_{i-1}-\langle
u_{i-1},u_{i}\rangle B_{i}}{\sin(\theta_{i}-\theta_{i-1})}$
$\displaystyle=\sum_{i=1}^{m}\frac{B_{i+1}-\cos(2\pi/m)B_{i}}{\sin(2\pi/m)}+\frac{B_{i-1}-\cos(2\pi/m)B_{i}}{\sin(2\pi/m)}$
$\displaystyle=\frac{1}{\sin(2\pi/m)}\left(\sum_{i=1}^{m}B_{i+1}+\sum_{i=1}^{m}B_{i-1}-2\sum_{i=1}^{m}\cos(2\pi/m)B_{i}\right)$
$\displaystyle=(2m)\frac{1-\cos(2\pi/m)}{\sin(2\pi/m)}\sum_{i=1}^{m}B_{i}/m.$

Since any optimal $(B_{i})_{i=1}^{m}$ would minimise $\sum_{i}w_{i}B_{i}$ it
must also minimise $\sum_{i}L_{i}$, making them equivalent objective functions
in this case. For a uniformly distributed $\mathcal{S}$, we have that the
optimal weights, $W=\\{w_{i}\\}_{i=1}^{m}$, $w_{i}=1/m$, yield at least a
$\frac{\pi}{2m}$-accurate quadrature. Using the quadrature $(\mathcal{S},W)$
will therefore allow us to optimise both mean width and circumference with
optimal accuracy. In addition, we can use the efficient formulation of (7.3)
which significantly increases the computation speed.

##  8\. Approximating the mean width

In this section, we approximate the mean width of a convex shape using point
samples in the sense of 3.6.

In two dimensions, the simplest example of an $\epsilon$-accurate quadrature
is the uniform quadrature $\left\\{\Big{(}\big{(}\cos\left(\frac{2\pi
i}{m}\right),\sin\left(\frac{2\pi
i}{m}\right)\big{)},\frac{1}{m}\Big{)}\right\\}_{i=1}^{m}\subset S^{N-1}$. To
see this, we bound the difference (3.1). By symmetry, we can split the
integral into $2m$ identical segments of $\frac{2\pi}{2m}$ radians each, where
each part has one endpoint on a quadrature point. Using the fact that $f$ is
$L$-Lipschitz, the approximation error is hence at most

$\displaystyle\frac{2m}{2\pi}\int_{0}^{\frac{2\pi}{2m}}L\sqrt{\sin^{2}(\theta)+(1-\cos(\theta))^{2}}\,d\theta=\frac{8Lm}{\pi}\sin^{2}\left(\frac{\pi}{4m}\right)\leq\frac{\pi}{2m}L.$

Hence, the uniform quadrature in two dimensions is $\frac{\pi}{2m}$-accurate.
It is also straightforward to see that the uniform quadrature has dispersion
$2\sin\left(\frac{\pi}{2m}\right)<\frac{\pi}{m}$.

As concrete examples of accurate quadratures in general dimensions, we may use
the composite midpoint rule on the cubed hypersphere, which is defined as
follows. Let $s\in\mathbb{N}^{+}$ be the number of subdivisions per dimension.
Let $U=\left\\{\frac{2i-s-1}{s}\colon i\in\\{1,\dots,s\\}\right\\}$ denote $s$
uniformly distributed points on the segment $[-1,1]$. Then we can define a
grid on the faces orthogonal on the $i$th dimension of the hypercube by taking
Cartesian products

$v_{i}\coloneqq\underbrace{U\times\cdots\times U}_{i-1\text{
times}}\times\\{-1,1\\}\times\underbrace{U\times\cdots\times U}_{N-i\text{
times}}.$

The combined grid becomes $V\coloneqq\bigcup_{i=1}^{N}v_{i}$. We number the
points in $V$ from $1$ to $m\coloneqq 2Ns^{N-1}$. Then,
$\left\\{\left(\frac{1}{\left\|V_{i}\right\|_{2}}V_{i},\frac{1}{\left\|V_{i}\right\|_{2}}\left(\frac{2}{s}\right)^{N-1}\right)\right\\}_{i=1}^{m}\subset
S^{N-1}$ defines a quadrature which we call the cubed hypersphere quadrature
with $s$ subdivisions.

######  Proposition 8.1.

The cubed hypersphere quadrature with $s$ subdivisions is
$\frac{N2^{N}\sqrt{N-1}}{s}$-accurate and has dispersion bounded by
$\frac{\sqrt{N-1}}{s}$.

The proof is deferred to the end of this section.

Once we have an $\epsilon$-accurate quadrature, we can transform any set
$\\{u\\}_{i=1}^{m}$ with small dispersion into an accurate quadrature using
the following.

######  Proposition 8.2.

Let $\mathcal{S}=\\{u_{i}\\}_{i=1}^{m}\subset S^{N-1}$ have dispersion
$\delta=\mathrm{disp}(\mathcal{S})$, and $\\{(v_{j},z_{j})\\}_{j=1}^{m}$ be an
$\epsilon$-accurate quadrature. For $j=1,\dots,m$, let $p_{j}$ be the index of
a point in $\mathcal{S}$ closest to $v_{j}$. Let
$p^{-1}_{i}\coloneqq\left\\{j\in\\{1,\dots,m\\}\colon p_{j}=i\right\\}$ be a
set of indices of points in $\\{v_{j}\\}_{j=1}^{m}$ closest to $u_{i}$. For
$i=1,\dots,m$, let $w_{i}=\sum_{j\in p^{-1}_{i}}z_{j}$. Then
$\\{(u_{i},w_{i})\\}_{i=1}^{m}$ is a $\delta+\epsilon(1+\delta)$-accurate
quadrature.

###### Proof.

Let $f\colon S^{N-1}\to\mathbb{R}$ be $L$-Lipschitz and have absolute value
bounded by $\left\|f\right\|_{\infty}$, then since
$\\{(v_{j},z_{j})\\}_{j=1}^{m}$ is an $\epsilon$-accurate quadrature, we have

$\displaystyle\left|\int_{S}f(u)\,d\sigma(u)-\sum_{j=1}^{m}f(v_{j})z_{j}\right|\leq\epsilon(L+\left\|f\right\|_{\infty}).$
(8.1)

Expanding the definitions of $w_{i}$ and $p^{-1}$, we get

$\displaystyle\sum_{i=1}^{m}f(u_{i})w_{i}$
$\displaystyle=\sum_{i=1}^{m}f(u_{i})\sum_{j\in
p^{-1}_{i}}z_{j}=\sum_{i=1}^{m}\sum_{j\in
p^{-1}_{i}}f(v_{j})z_{j}+z_{j}(f(u_{i})-f(v_{j}))$
$\displaystyle=\sum_{j=1}^{m}f(v_{j})z_{j}+\sum_{j=1}^{m}z_{j}(f(u_{p_{j}})-f(v_{j})).$

The second term can be bounded by $f$ being Lipschitz continuous, giving

$\displaystyle\left|\sum_{j=1}^{m}z_{j}(f(u_{p_{j}})-f(v_{j}))\right|\leq\sum_{j=1}^{m}z_{j}L\left\|u_{p_{j}}-v_{j}\right\|_{2}.$

Furthermore, by the definition of $p_{j}$ as the index of a closest points in
$\mathcal{S}$, and the definition of $\mathrm{disp}(\mathcal{S})$, we have
$\left\|u_{p_{j}}-v_{j}\right\|_{2}\leq\delta$ for $j=1,\dots,m$. Finally, we
can bound $\sum_{j=1}^{m}z_{j}\leq 1+\epsilon$ by inserting the constant
function $f=1$ into (8.1).

Combining everything, we get

$\displaystyle\left|\int_{S}f(u)\,d\sigma(u)-\sum_{j=1}^{m}f(u_{j})w_{j}\right|$
$\displaystyle\leq\left|\int_{S}f(u)\,d\sigma(u)-\sum_{j=1}^{m}f(v_{j})z_{j}\right|+\delta
L(1+\epsilon)$ $\displaystyle\leq\epsilon(L+\left\|f\right\|_{\infty})+\delta
L(1+\epsilon)$
$\displaystyle\leq(\delta+\epsilon(1+\delta))(L+\left\|f\right\|_{\infty}).$

Which is the definition of being a $\delta+\epsilon(1+\delta)$-accurate
quadrature. ∎

### Proof of 8.1

###### Proof.

Let $F_{i}$ denote the $i$th of the $2N$ faces of t he hypercube in $N$
dimensions and let $S_{i}$ be its projection on the unit hypersphere
$S^{N-1}$. Then,

$\displaystyle\int_{S^{N-1}}f(u)\,d\sigma(u)=\sum_{i=1}^{2N}\int_{S_{i}}f(u)\,d\sigma(u).$

We perform a transformation of variables $u=\frac{1}{\left\|v\right\|_{2}}v$
to transform the integral over $S_{i}$ to one over $F_{i}$.

$\displaystyle\int_{S_{i}}f(u)\,d\sigma(u)=\int_{F_{i}}f\left(\frac{1}{\left\|v\right\|_{2}}v\right)\frac{1}{\left\|v\right\|_{2}}\,dv.$
(8.2)

The cubed hypersphere quadrature corresponds to approximating the integral
(8.2) with the composite midpoint rule. That is, the integral is divided into
$s^{N-1}$ hypercubes with side lengths $\frac{2}{s}$, each approximated by the
value at their midpoint. Let the $j$th of these hypercubes be called $F_{ij}$.

$\displaystyle\int_{F_{i}}f\left(\frac{1}{\left\|v\right\|_{2}}v\right)\frac{1}{\left\|v\right\|_{2}}\,dv=\sum_{j=1}^{s^{N-1}}\int_{F_{ij}}f\left(\frac{1}{\left\|v\right\|_{2}}v\right)\frac{1}{\left\|v\right\|_{2}}\,dv.$

Note that for all $v\in F_{i}$, we have $\left\|v\right\|_{2}\geq 1$. So since
$f$ is $L$-Lipschitz, $f\left(\frac{1}{\left\|v\right\|_{2}}v\right)$ is also
$L$-Lipschitz for $v\in F_{i}$. Additionally, $\frac{1}{\left\|v\right\|_{2}}$
is $1$-Lipschitz for $v\in F_{i}$. Hence, for $u,v\in F_{i}$,

$\displaystyle\left|f\left(\frac{1}{\left\|u\right\|_{2}}u\right)\frac{1}{\left\|u\right\|_{2}}-f\left(\frac{1}{\left\|v\right\|_{2}}v\right)\frac{1}{\left\|v\right\|_{2}}\right|$
$\displaystyle\leq$
$\displaystyle\left|f\left(\frac{1}{\left\|u\right\|_{2}}u\right)-f\left(\frac{1}{\left\|v\right\|_{2}}v\right)\right|\frac{1}{\left\|u\right\|_{2}}+\left|f\left(\frac{1}{\left\|v\right\|_{2}}v\right)\left(\frac{1}{\left\|u\right\|_{2}}-\frac{1}{\left\|v\right\|_{2}}\right)\right|$
$\displaystyle\leq$
$\displaystyle\left\|u-v\right\|_{2}(L+\left\|f\right\|_{\infty}).$

So
$f\left(\frac{1}{\left\|v\right\|_{2}}v\right)\frac{1}{\left\|v\right\|_{2}}$
is Lipschitz over $F_{i}$ with constant $L+\left\|f\right\|_{\infty}$, where
$\left\|f\right\|_{\infty}$ is an upper bound on the absolute value of $f$.
Consider the $j$th hypercube, let its midpoint be $V_{j}$. Inside the
hypercube, the maximum distance to the midpoint is $\frac{\sqrt{N-1}}{s}$, so
we get an error bounded by
$\frac{\sqrt{N-1}}{s}(L+\left\|f\right\|_{\infty})$. Specifically,

$\displaystyle\left|\int_{F_{ij}}f\left(\frac{1}{\left\|v\right\|_{2}}v\right)\frac{1}{\left\|v\right\|_{2}}\,dv-\int_{F_{ij}}f\left(\frac{1}{\left\|V_{j}\right\|_{2}}V_{j}\right)\frac{1}{\left\|V_{j}\right\|_{2}}\,dv\right|$
$\displaystyle\leq\int_{F_{ij}}\frac{\sqrt{N-1}}{s}(L+\left\|f\right\|_{\infty})\,dv.$

Next, note that the volume of $F_{ij}$ is $\left(\frac{2}{s}\right)^{N-1}$, so

$\displaystyle\int_{F_{ij}}f\left(\frac{1}{\left\|V_{i}\right\|_{2}}V_{i}\right)\frac{1}{\left\|V_{i}\right\|_{2}}\,dv=f\left(\frac{1}{\left\|V_{i}\right\|_{2}}V_{i}\right)\
\frac{1}{\left\|V_{i}\right\|_{2}}\left(\frac{2}{s}\right)^{N-1}=f(u_{i})w_{i},$

where $u_{i}$ and $w_{i}$ are the cubed hypersphere quadrature. Hence the
$i$th hypercube contributes an error at most

$\displaystyle\left|\int_{F_{ij}}f\left(\frac{1}{\left\|v\right\|_{2}}v\right)\frac{1}{\left\|v\right\|_{2}}\,dv-f(u_{i})w_{i}\right|\leq\frac{\sqrt{N-1}}{s}(L+\left\|f\right\|_{\infty})\left(\frac{2}{s}\right)^{N-1}.$

Summing over the $m=2Ns^{N-1}$ hypercubes, we get an error at most

$\displaystyle\left|\int_{S}f(u)\,d\sigma(u)-\sum_{i=1}^{m}f(u)w_{i}\right|$
$\displaystyle\leq
2Ns^{N-1}\frac{\sqrt{N-1}}{s}(L+\left\|f\right\|_{\infty})\left(\frac{2}{s}\right)^{N-1}$
$\displaystyle=\frac{N2^{N}\sqrt{N-1}}{s}(L+\left\|f\right\|_{\infty}).$

Hence the quadrature is $\frac{N2^{N}\sqrt{N-1}}{s}$-accurate.

The dispersion can also be bounded by considering the hypercubes $F_{ij}$.
Again, all points in the $j$th hypercube of the $i$th face are within a
distance $\frac{\sqrt{N-1}}{s}$ from the midpoint. Distances in the hypercube
only get smaller when they are projected onto the unit hypersphere $S^{N-1}$,
and the projected midpoints are exactly the cubed hypersphere quadrature
points. Hence, the dispersion is bounded by $\frac{\sqrt{N-1}}{s}$. ∎

##  9\. Conclusion and Final Remarks

In conclusion, this paper has presented a novel algorithm for the computation
of valid environmental contours. The proposed algorithm ensures that the
contours satisfy the outreach requirements while maintaining a minimal mean
width. We have also presented a streamlined algorithm for two dimensions,
which improves computation speed for this specific case. Both of the
considered methods have been illustrated by numerical examples.

Furthermore, as these methods rely on numerical integration, we also provided
a generic construction for making arbitrarily accurate quadratures.

Lastly, rigorous examination of convergence and existence of solutions has
been conducted, ensuring the reliability and accuracy of the proposed methods.
Convergence properties have been thoroughly analyzed, including the
convergence of the optimal approximate mean width to the optimal mean width,
as well as convergence in terms of the Hausdorff metric. These analyses ensure
that any approximate solution will give an arbitrarily near-optimal contour,
and that any optimal contour can be found by searching the near-optimal
approximations.

## Acknowledgements

The authors acknowledge financial support by the Research Council of Norway
under the SCROLLER project, project number 299897 (Åsmund Hausken Sande).

## References

  * [1]
  * [1] Baarholm, G. S. ; Haver, S. ; Økland, O. D.:  Combining contours of significant wave height and peak period with platform response distributions for predicting design response.  In: _Marine Structures_ 23 (2010), Nr. 2, S. 147–163
  * [2] Dahl, K. R. ; Huseby, A. B.:  Buffered environmental contours.  In: _Safety and Reliability–Safe Societies in a Changing World_.  CRC Press, 2018, S. 2285–2292
  * [3] DNV:  _Recommended Practice DNV-RP-C205 on environmental conditions and environmental loads_.  Det Norske Veritas Oslo, Norway, Sep, 2019 (Amended: Sep, 2021)
  * [4] Fontaine, E. ; Orsero, P. ; Ledoux, A. ; Nerzic, R. ; Prevosto, M. ; Quiniou, V. :  Reliability analysis and response based design of a moored FPSO in West Africa.  In: _Structural Safety_ 41 (2013), S. 82–96
  * [5] Giske, F.-I. G. ; Kvåle, K. A. ; Leira, B. J. ; Øiseth, O. :  Long-term extreme response analysis of a long-span pontoon bridge.  In: _Marine Structures_ 58 (2018), S. 154–171
  * [6] Hafver, A. ; Agrell, C. ; Vanem, E. :  Environmental contours as Voronoi cells.  In: _Extremes_ 25 (2022), Nr. 3, S. 451–486
  * [7] Haselsteiner, A. F. ; Coe, R. G. ; Manuel, L. ; Chai, W. ; Leira, B. ; Clarindo, G. ; Soares, C. G. ; Hannesdóttir, Á. ; Dimitrov, N. ; Sander, A. u. a.:  A benchmarking exercise for environmental contours.  In: _Ocean Engineering_ 236 (2021), S. 109504
  * [8] Haver, S. ; Winterstein, S. R.:  Environmental contour lines: A method for estimating long term extremes by a short term analysis.  In: _SNAME Maritime Convention_ SNAME, 2008, S. D011S002R005
  * [9] Huseby, A. B.:  Environmental contours and time dependence.  In: _Proceedings of the 33nd European Safety and Reliability Conference_ , 2023, S. 1290–1297
  * [10] Huseby, A. B. ; Vanem, E. ; Agrell, C. ; Hafver, A. :  Convex environmental contours.  In: _Ocean Engineering_ 235 (2021), S. 109366
  * [11] Huseby, A. B. ; Vanem, E. ; Natvig, B. :  A new approach to environmental contours for ocean engineering applications based on direct Monte Carlo simulations.  In: _Ocean Engineering_ 60 (2013), S. 124–135
  * [12] Huseby, A. B. ; Vanem, E. ; Natvig, B. :  Alternative environmental contours for structural reliability analysis.  In: _Structural Safety_ 54 (2015), S. 32–45
  * [13] Leira, B. J.:  A comparison of stochastic process models for definition of design contours.  In: _Structural Safety_ 30 (2008), Nr. 6, S. 493–505
  * [14] Mackay, E. ; Hauteclocque, G. de:  Model-free environmental contours in higher dimensions.  In: _Ocean Engineering_ 273 (2023), S. 113959
  * [15] Price, G. B.:  On the completeness of a certain metric space with an application to Blaschke’s selection theorem.  (1940)
  * [16] Rockafellar, R. T.:  _Convex analysis_. Bd. 11.  Princeton university press, 1997
  * [17] Ross, E. ; Astrup, O. C. ; Bitner-Gregersen, E. ; Bunn, N. ; Feld, G. ; Gouldby, B. ; Huseby, A. ; Liu, Y. ; Randell, D. ; Vanem, E. u. a.:  On environmental contours for marine and coastal design.  In: _Ocean Engineering_ 195 (2020), S. 106194
  * [18] Sagrilo, L. ; Naess, A. ; Doria, A. :  On the long-term response of marine structures.  In: _Applied Ocean Research_ 33 (2011), Nr. 3, S. 208–214
  * [19] Sande, Å. H. :  Convex Environmental Contours for Non-Stationary Processes.  In: _arXiv preprint arXiv:2305.09239_ (2023)
  * [20] Vanem, E. :  3-dimensional environmental contours based on a direct sampling method for structural reliability analysis of ships and offshore structures.  In: _Ships and Offshore Structures_ 14 (2019), Nr. 1, S. 74–85
  * [21] Vanem, E. :  Analysing multivariate extreme conditions using environmental contours and accounting for serial dependence.  In: _Renewable Energy_ 202 (2023), S. 470–482
  * [22] Vanem, E. ; Bitner-Gregersen, E. M.:  Stochastic modelling of long-term trends in the wave climate and its potential impact on ship structural loads.  In: _Applied Ocean Research_ 37 (2012), S. 235–248
  * [23] Winterstein, S. R. ; Ude, T. C. ; Cornell, C. A. ; Bjerager, P. ; Haver, S. :  Environmental parameters for extreme response: Inverse FORM with omission factors.  In: _Proceedings of the ICOSSAR-93, Innsbruck, Austria_ (1993), S. 551–557