A Canonical Reciprocation Center
For Convex Objects

Don Hatch
hatch@plunk.org


Date: (draft)
Last modified: Wed Jun 4 21:36:24 PDT 2003

Abstract:

A canonical reciprocation center function for a class of geometric objects is a function assigning to each object a ``canonical center'' point, such that if $ \vec{c}$ is the canonical center of $ P$, and $ P^*$ is the reciprocal of $ P$ with respect to a hypersphere of any radius centered at $ \vec{c}$, then the canonical center of $ P^*$ is also $ \vec{c}$.

We present a canonical reciprocation center function for compact (closed and bounded) convex subsets of $ \mathbb{R}^n$ with non-empty interior. This function is continuous under continous deformations of the compact convex set, and it commutes with rotations, translations, reflections, and uniform scalings of $ \mathbb{R}^n$. This answers a $1000 question posed by John Conway [1].

[ XXX is there a way to say the commuting thing more concisely? ``commutes with shape-preserving transformations on $ R^n$''?]

Introduction

Two polyhedra $ P$ and $ Q$ are said to be duals of each other if there is a 1-to-1 incidence-preserving correspondence between the (faces, edges, vertices) of $ P$ and the (vertices, edges, faces) of $ Q$, respectively.

When examining the structure of a polyhedron, it is often useful to examine its dual polyhedron at the same time. For example, the computer program Stella [XXX ref] allows viewing and manipulating a (``primal'') polyhedron $ P$ and its dual polyhedron $ Q$, either side-by-side, or superimposed.

However, the dual polyhedron $ Q$, being defined only by its structure (i.e. incidences among its boundary elements) in relation to $ P$, is not geometrically unique: for example, starting with any particular dual $ Q$ of $ P$, any affine squashing, stretching, or shearing of $ Q$ results in a new polyhedron that equally well satisfies the definition of dual of $ P$. More exotic deformations of $ \mathbb{R}^3$ result in a wide range of possible duals for any particular polyhedron.

So such a program or presentation has a choice to make: which dual to present, for a given primal polyhedron $ P$?

First, note that it is not obvious that every polyhedron has a dual polyhedron at all. We will henceforth restrict our attention to convex polyhedra: for this class of polyhedra, we can use the process of reciprocation about a sphere (which we will define in Section 2 [XXX get xref right]) to produce a dual polyhedron $ Q$; furthermore, reciprocating $ Q$ about the same sphere yields $ P$ again.

However, the process of reciprocation still leaves some freedom: it requires a choice of reciprocation center (which can be any point in the interior of $ P$) and reciprocation radius. The radius is not particularly problematic: for a given reciprocation center, changing the reciprocation radius simply results in a larger or smaller reciprocal polyhedron $ Q$, without changing its shape or orientation. So a reasonable choice for radius might be one that equalizes some measure of the sizes of $ P$ and $ Q$, say, their volumes, surface areas, or average distances from the reciprocation center (measured in any of various ways).

The choice of reciprocation center, on the other hand, is surprisingly problematic. Since the duality relation is symmetric, it seems reasonable and desirable to try to make our canonical-dual-choosing process symmetric as well. But obvious choices of reciprocation center violate this desired symmetry. For example, let's look at what happens when we try using the centroid (center of mass) of the primal polyhedron as the reciprocation center. Starting with $ P$, we find its centroid $ \vec{c}\left(P\right)$ and reciprocate about a sphere centered at $ \vec{c}\left(P\right)$ to get the reciprocal polyhedron $ Q$. Then we find the centroid $ \vec{c}\left(Q\right)$ of $ Q$ and reciprocate $ Q$ about a sphere centered there to get a polyhedron $ P'$. $ P'$ has the same structure as $ P$ (since they are both dual to $ Q$, which specifies their structure), but in general they will not have the same shape, unless $ \vec{c}\left(Q\right)$ happens to equal $ \vec{c}\left(P\right)$, which is not true in general. Various other naïve attempts result in exactly the same problem, and one becomes tempted to believe that no well-behaved center-choosing strategy exists.

Note that in the special case when $ P$ has a center of symmetry $ c$ (i.e. a unique point that is fixed by all symmetries of $ P$), then there is no issue: $ c$ is the natural choice, and in fact it is the only possible choice, assuming we want behavior independent of the orientation of $ P$. This is the case for the regular (Platonic) and uniform (Archimedian) polyhedra. So the difficulty arises when we start looking at more general polyhedra without centers of symmetry, e.g. certain of the Johnson solids (convex polyhedra whose faces are regular polygons) [XXX ref].

Our task is to find a canonical reciprocation center function: that is, a function assigning to each convex polyhedron a point in its interior suitable for use as a reciprocation center. In particular, it must satisfy the desired symmetric behavior described above, as well as a reasonable continuity condition- continuous changes in $ P$ must not result in jumps of the reciprocation center! At this point, it is not obvious that any such function exists.

In this paper, will construct such a function. [XXX should mention that the function has even better/stronger continuity than might be expected: it does not jump even if the topology of the polyhedron changes, e.g. when a face is subdivided by addition of a new edge.] The construction and proof works not just for convex polyhedra, but for all compact (i.e. closed and bounded) convex subsets of $ \mathbb{R}^n$ $ \left(n \geq 1\right)$ with non-empty interior. So we start with the following definitions.

Definitions: For $ n \geq 1$, let

$\displaystyle {\mathcal{P}^n}=$ $\displaystyle \left\{P \subset \mathbb{R}^n : \text{$P$\ is compact (closed and bounded), convex,}\right.$    
  $\displaystyle \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \: \left.\text{and has non-empty interior}\right\}.$    
$\displaystyle {\mathcal{P}^n_0}=$ $\displaystyle \left\{P \in {\mathcal{P}^n}: \text{$\vec{0}\in \mathit{int}\left(P\right)$}\right\}.$    

where $ \mathit{int}\left(P\right)$ denotes the interior of $ P$.

Reciprocation

Definitions: If $ P \in {\mathcal{P}^n_0}$, we define the reciprocal $ {P^{-1}}$ of $ P$ about the unit hypersphere as:

$\displaystyle {P^{-1}}= \left\{\vec{q}\in \mathbb{R}^n : \forall \vec{p}\!\in\! P \; \vec{p}\cdot \vec{q}\leq 1 \right\}.$    

[ XXX warn not to call it ``inverse'' or you will be spanked ]

It easily follows from the definition that reciprocation reverses scale; that is, for $ r > 0$:

$\displaystyle \left(r P\right)^{-1}= \frac{{P^{-1}}}{r}$ (1)

where $ r P = \left\{r \vec{p}: \vec{p}\in P\right\}.$

It is also straightforward to check that $ {P^{-1}}$ is compact and convex, and contains $ \vec{0}$ in its interior; i.e. $ {P^{-1}}\in {\mathcal{P}^n_0}$ and so $ {\left(P^{-1}\right)^{-1}}$ is defined.

Lemma 2.1   For all $ P \in {\mathcal{P}^n_0}$, $ {\left(P^{-1}\right)^{-1}}= P$.

Proof of Lemma 2.1: For all $ \vec{v}\in \mathbb{R}^n$, let $ \mathcal{H}\left(\vec{v}\right) = \left\{\vec{w}\in \mathbb{R}^n : \vec{w}\cdot \vec{v}\leq 1\right\}$. Note that $ \left\{\mathcal{H}\left(\vec{v}\right) : \vec{v}\in \mathbb{R}^n \setminus \left\{\vec{0}\right\}\right\}$ is precisely the set of closed half-spaces containing the origin in their interiors, and  $ \mathcal{H}\left(\vec{0}\right) = \mathbb{R}^n$. Note also the following duality correspondence: for all $ \vec{v},\vec{w}\in \mathbb{R}^n$,

$\displaystyle \vec{w}\in \mathcal{H}\left(\vec{v}\right) \Longleftrightarrow \v...
...t \vec{w}\leq 1 \Longleftrightarrow \vec{v}\in \mathcal{H}\left(\vec{w}\right).$ (2)

Then, given $ P \in {\mathcal{P}^n_0}$,

$\displaystyle {P^{-1}}$ $\displaystyle = \left\{\vec{q}\in R^n : \forall \vec{p}\!\in\! P \; \vec{p}\cdot \vec{q}\leq 1\right\} \;\;\;\;$   by definition    
  $\displaystyle = \left\{\vec{q}\in \mathbb{R}^n : \forall \vec{p}\!\in\! P \; \vec{q}\in \mathcal{H}\left(\vec{p}\right)\right\} \;\;\;\;$   by (2)    
  $\displaystyle = \bigcap \left\{\mathcal{H}\left(\vec{p}\right) : \vec{p}\in P\right\}.$ (3)

On the other hand,

$\displaystyle {P^{-1}}$ $\displaystyle = \left\{\vec{q}\in \mathbb{R}^n : \forall \vec{p}\!\in\! P \; \vec{p}\cdot \vec{q}\leq 1\right\} \;\;\;\;$   by definition    
  $\displaystyle = \left\{\vec{q}\in \mathbb{R}^n : \forall \vec{p}\!\in\! P \; \vec{p}\!\in\! \mathcal{H}\left(\vec{q}\right)\right\} \;\;\;\;$   by (2)    
  $\displaystyle = \left\{\vec{q}\in \mathbb{R}^n : P \subset \mathcal{H}\left(\vec{q}\right)\right\}.$ (4)

Combining these two ways of looking at reciprocation, we get:

$\displaystyle {\left(P^{-1}\right)^{-1}}$ $\displaystyle = \bigcap \left\{\mathcal{H}\left(\vec{q}\right) : \vec{q}\in {P^{-1}}\right\} \;\;\;\;$   by (3)    
  $\displaystyle = \bigcap \left\{\mathcal{H}\left(\vec{q}\right) : \vec{q}\in \mathbb{R}^n \hbox{ and } P \subset \mathcal{H}\left(\vec{q}\right)\right\} \;\;\;\;$   by (5)    
  $\displaystyle = \bigcap \left\{\mathcal{H}\left(\vec{q}\right) : \vec{q}\in \ma...
...\vec{0}\right\} \hbox{ and } P \subset \mathcal{H}\left(\vec{q}\right)\right\},$    

the last equality holding since $ \mathcal{H}\left(\vec{0}\right) = \mathbb{R}^n$ does not affect the intersection. In other words,

$\displaystyle {\left(P^{-1}\right)^{-1}}$ $\displaystyle = \bigcap \left\{\mathcal{H}: \text{$\mathcal{H}$\ is a closed ha...
...in \mathit{int}\left(\mathcal{H}\right)$, and~$P \subset \mathcal{H}$} \right\}$    
  $\displaystyle = \bigcap \left\{\mathcal{H}: \text{$\mathcal{H}$\ is a closed ha...
...l{H}$} \right\}, \;\;\;\; \text{since $\vec{0}\in \mathit{int}\left(P\right)$}.$    

So $ {\left(P^{-1}\right)^{-1}}$ is the intersection of all closed half-spaces that contain $ P$; that is, $ {\left(P^{-1}\right)^{-1}}$ is the closure of the convex hull of $ P$. But $ P$ is already convex and closed, so $ {\left(P^{-1}\right)^{-1}}= P$. $ \square$

The proof of Lemma 2.1 used the generally useful fact that $ {P^{-1}}$ can be thought of in two ways: either as the intersection of all closed halfspaces $ \mathcal{H}\left(\vec{p}\right)$ corresponding to points $ \vec{p}\in P$, or as the set of all points $ \vec{q}$ corresponding to the closed halfspaces $ \mathcal{H}\left(\vec{q}\right)$ containing $ P$. Boundary points of $ P$ correspond to bounding planes of $ {P^{-1}}$ and vice-versa. In particular, if $ P$ is a polygon or polyhedron, then so is $ {P^{-1}}$, and the vertices of $ P$ correspond to the sides or faces of $ {P^{-1}}$ and vice-versa.

We now generalize the definition of reciprocation about the unit hypersphere to that of reciprocation about an arbitrarily sized hypersphere centered anywhere in the interior of $ P$ ($ P$ may or may not contain the origin), as follows. To reciprocate about a hypersphere, given the hypersphere's center $ \vec{c}\in \mathit{int}\left(P\right)$ and radius $ r > 0$, we translate and scale $ \mathbb{R}^n$ so that the hypersphere has center $ \vec{0}$ and radius $ 1$, reciprocate, and then apply the inverse scale and translation. Writing this out and applying (1), we get, for all $ P \in {\mathcal{P}^n}$, $ \vec{c}\in \mathit{int}\left(P\right)$, and $ r > 0$:

$\displaystyle \mathit{reciprocal}\left(P,\vec{c},r\right)$ $\displaystyle = \vec{c}+ r \left(\frac{P-\vec{c}}{r}\right)^{-1}$    
  $\displaystyle = \vec{c}+ r^2 \left(P-\vec{c}\right)^{-1}.$ (5)

Then of course $ \mathit{reciprocal}\left(P,\vec{0},1\right)
=
{P^{-1}}
$. [Pictures of reciprocals needed! This paper is self-contained so should try to be helpful to people unfamiliar with reciprocals!]

Definition: If $ P \in {\mathcal{P}^n_0}$ and  $ \vec{v}\in \mathbb{R}^n \setminus \left\{\vec{0}\right\}$, let $ r_P\left(\vec{v}\right)$ denote the (positive) distance from the origin to the boundary of $ P$ in the direction of $ \vec{v}$.

Lemma 2.2   If $ P \in {\mathcal{P}^n_0}$, then for all $ \vec{u}\in \mathbb{R}^n$ such that $ \left\Vert\vec{u}\right\Vert = 1$,

$\displaystyle r_{P^{-1}}\left(\vec{u}\right) = {1 \; / \max_{\vec{p}\in P} \left(\vec{p}\cdot \vec{u}\right)}.$    

Proof of Lemma 2.2: If $ P \in {\mathcal{P}^n_0}$ and $ \left\Vert\vec{u}\right\Vert = 1$, then

$\displaystyle \max_{\vec{p}\in P} \left(\vec{p}\cdot \vec{u}\right) =$ $\displaystyle \sup \left\{ s \geq 0 : \exists \vec{p}\!\in\! P \; \vec{p}\cdot \vec{u}> s \right\}$    
$\displaystyle =$ $\displaystyle \inf \left\{ s \geq 0 : \forall \vec{p}\!\in\! P \; \vec{p}\cdot \vec{u}\leq s \right\} \;\;\;\;$   since $ P$ is connected,    
  $\displaystyle \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \;$   bounded, and contains $ \vec{0}$    
$\displaystyle =$ $\displaystyle \inf \left\{ \frac{1}{r} \geq 0 : \forall \vec{p}\!\in\! P \; \vec{p}\cdot \vec{u}\leq \frac{1}{r} \right\}$    
$\displaystyle =$ $\displaystyle \; 1 \, / \sup \left\{ r \geq 0 : \forall \vec{p}\!\in\! P \; \vec{p}\cdot \vec{u}\leq \frac{1}{r} \right\}$    
$\displaystyle =$ $\displaystyle \; 1 \, / \sup \left\{ r \geq 0 : \forall \vec{p}\!\in\! P \; \vec{p}\cdot r \vec{u}\leq 1 \right\}$    
$\displaystyle =$ $\displaystyle \; 1 \, / \sup \left\{ r \geq 0 : r \vec{u}\in {P^{-1}}\right\}, \;\;\;\;$   by definition of $ {P^{-1}}$    
$\displaystyle =$ $\displaystyle \; 1 / r_{{P^{-1}}}\left(\vec{u}\right)$    
$\displaystyle r_{{P^{-1}}}\left(\vec{u}\right) =$ $\displaystyle \; 1 \; / \max_{\vec{p}\in P} \left(\vec{p}\cdot \vec{u}\right). \;\; \square$    

[XXX make corollary numbers in same sequence as lemma numbers!]

Corollary 2.1   If $ P \in {\mathcal{P}^n}$, then for all $ \vec{c}\in \mathit{int}\left(P\right)$ and  $ \vec{u}\in \mathbb{R}^n$ such that $ \left\Vert\vec{u}\right\Vert = 1$,

$\displaystyle r_{\left(P-\vec{c}\right)^{-1}}\left(\vec{u}\right) = {1 \; / \max_{\vec{p}\in P} \left(\left(\vec{p}-\vec{c}\right) \cdot \vec{u}\right)}.$    

Proof of Corollary 2.1: Use $ \left(P-\vec{c}\right)$ for the $ P$ of Lemma 2.2. $ \square$

A Canonical Reciprocation Center Function

Definition: Define $ f : {\mathcal{P}^n_0}\rightarrow \mathbb{R}^n$ by:

$\displaystyle f\left(P\right) = \int_{\vec{u}\in \mathbb{S}^{n-1}} \log\left(r_P\left(\vec{u}\right)\right) \vec{u}\; dA,$    

the integral being taken over the (hyper-) area as $ \vec{u}$ ranges over the unit hypersphere $ \mathbb{S}^{n-1}$ in $ \mathbb{R}^n$.

Intuitively, $ f\left(P\right)$ is the weighted average of all unit vectors, with each weight being equal to the logarithm (possibly negative) of the distance from the origin to the boundary of $ P$ in that direction.

$ f$ can be thought of as a vector-valued measure of the ``offcenteredness'' of $ P$ from the origin. In particular, note that when only one part of the boundary of $ P$ is very close to the origin, $ f\left(P\right)$ will be weighted heavily in the opposite direction due to the dominance of the negative logarithm in the direction of the boundary.

[ XXX mention that the log can be with respect to any base; changing the base multiplies $ f$ by a scalar, and all the results of this paper still hold, and the final reciprocation center is the same ]

A somewhat surprising property of $ f\left(P\right)$ is that it is impervious to scaling of $ P$, as the next Lemma shows.

Lemma 3.1   If $ P \in {\mathcal{P}^n_0}$ and $ s > 0$, then $ f\left(s P\right) = f\left(P\right)$, where $ s P = \left\{s \vec{p}: \vec{p}\in P\right\}$.

Proof of Lemma 3.1:

$\displaystyle f\left(s P\right)$ $\displaystyle = \int_{\vec{u}\in \mathbb{S}^{n-1}} \log\left(r_{s P}\left(\vec{u}\right)\right) \vec{u}\; dA$    
  $\displaystyle = \int_{\vec{u}\in \mathbb{S}^{n-1}} \log\left(s \; r_P\left(\vec{u}\right)\right) \vec{u}\; dA$    
  $\displaystyle = \int_{\vec{u}\in \mathbb{S}^{n-1}} \left(\log\left(s\right) + \log\left(r_P\left(\vec{u}\right)\right)\right) \vec{u}\; dA$    
  $\displaystyle = \log\left(s\right) \int_{\vec{u}\in \mathbb{S}^{n-1}} \vec{u}\;...
...c{u}\in \mathbb{S}^{n-1}} \log\left(r_P\left(\vec{u}\right)\right) \vec{u}\; dA$    
  $\displaystyle = \vec{0}+ \int_{\vec{u}\in \mathbb{S}^{n-1}} \log\left(r_P\left(\vec{u}\right)\right) \vec{u}\; dA$    
  $\displaystyle = f\left(P\right). \;\; \square$    

At this point, we remark that in our quest to produce a canonical reciprocation center, a reasonable approach might be to look for a (hopefully unique) point $ \vec{c}\in \mathit{int}\left(P\right)$ such that $ f\left(P-\vec{c}\right) = \vec{0}$, and hope that when we do the same to the reciprocal of $ P$ with respect to a sphere centered at $ \vec{c}$, the result is the same point $ \vec{c}$. Lemma 3.1 shows that the radius of reciprocation is irrelevant; that is, if this works for some radius than it will work for all radii.

Unfortunately, it turns out that it does not work, since it can be (and often is) that $ f\left(P\right) = \vec{0}$ and  $ f\left({P^{-1}}\right) \neq \vec{0}$. However, we will now use $ f$ to construct a similar function $ F$ that does not suffer from this problem.

Definition: Define $ F : {\mathcal{P}^n_0}\rightarrow \mathbb{R}^n$ by:

$\displaystyle F\left(P\right) = f\left(P\right) - f\left({P^{-1}}\right).$    

The next Lemma shows that the analogue of Lemma 3.1 holds for $ F$ instead of $ f$.

Lemma 3.2   If $ P \in {\mathcal{P}^n_0}$ and $ s > 0$, then $ F\left(s P\right) = F\left(P\right)$.

Proof of Lemma 3.2:

$\displaystyle F\left(s P\right)$ $\displaystyle = f\left(s P\right) - f\left(\left(s P\right)^{-1}\right)$    
  $\displaystyle = f\left(s P\right) - f\left(s^{-1} {P^{-1}}\right) \;\;\;\;$   by (1)    
  $\displaystyle = f\left(P\right) - f\left({P^{-1}}\right), \;\;\;\;$   by Lemma 3.1    
  $\displaystyle = F\left(P\right). \;\; \square$    

Lemma 3.3   If $ P \in {\mathcal{P}^n_0}$, then $ F\left({P^{-1}}\right) = -F\left(P\right)$.

Proof of Lemma 3.3:

$\displaystyle F\left({P^{-1}}\right)$ $\displaystyle = f\left({P^{-1}}\right) - f\left({\left(P^{-1}\right)^{-1}}\right)$    
  $\displaystyle = f\left({P^{-1}}\right) - f\left(P\right), \;\;\;\;$   by Lemma 2.1    
  $\displaystyle = - \left(f\left(P\right) - f\left({P^{-1}}\right)\right)$    
  $\displaystyle = -F\left(P\right). \;\; \square$    

Now we would like to show that for all $ P \in {\mathcal{P}^n}$, there is a unique $ \vec{c}\in \mathit{int}\left(P\right)$ such that $ F\left(P-\vec{c}\right) = \vec{0}$. This will be established by the next two Lemmas.

Definition: For $ P \in {\mathcal{P}^n}$, define $ F_P : \mathit{int}\left(P\right) \rightarrow \mathbb{R}^n$ by:

$\displaystyle F_P\left(\vec{c}\right) = F\left(P-\vec{c}\right).$    

Lemma 3.4   For all $ P \in {\mathcal{P}^n}$, $ F_P$ is one-to-one.

[XXX I think this proof would look less cluttered if c wasn't throughout it. So, should argue for when c = 0 and then generalize (perhaps as a corollary). Note this is fine for the refs to (8) and (10) later in Lemma 3.5 since they only use the c=0 case. ] Proof of Lemma 3.4: Given $ P \in {\mathcal{P}^n}$, $ \vec{c}\in \mathit{int}\left(P\right)$, $ \varepsilon>0$, and  $ \vec{v}\in \mathbb{R}^n$ such $ \left\Vert\vec{v}\right\Vert = 1$ and  $ \vec{c}+ \varepsilon \vec{v}\in \mathit{int}\left(P\right)$, we must show that $ F_P\left(\vec{c}+ \varepsilon \vec{v}\right) \neq F_P\left(\vec{c}\right)$. We will do this by showing that

$\displaystyle \left(F_P\left(\vec{c}+ \varepsilon \vec{v}\right) - F_P\left(\vec{c}\right)\right) \cdot \vec{v}< 0.$    

By definition of $ F_P$ and $ F$,

$\displaystyle \left(F_P\left(\vec{c}+ \varepsilon \vec{v}\right) - F_P\left(\vec{c}\right)\right) \cdot \vec{v}=$ $\displaystyle \left(F\left(P-\left(\vec{c}+ \varepsilon \vec{v}\right)\right) - F\left(P-\vec{c}\right)\right) \cdot \vec{v}$    
$\displaystyle =$ $\displaystyle \left(\left(f\left(P-\left(\vec{c}+\varepsilon \vec{v}\right)\rig...
...ft(P-\left(\vec{c}+\varepsilon \vec{v}\right)\right)^{-1}\right)\right) \right.$    
  $\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; - \left. \left(f\left(P-...
...\right) - f\left(\left(P-\vec{c}\right)^{-1}\right)\right)\right) \cdot \vec{v}$    
$\displaystyle =$ $\displaystyle \left(f\left(P-\left(\vec{c}+\varepsilon \vec{v}\right)\right) - f\left(P-\vec{c}\right)\right) \cdot \vec{v}$    
$\displaystyle -$ $\displaystyle \left(f\left(\left(P-\left(\vec{c}+\varepsilon \vec{v}\right)\right)^{-1}\right) - f\left(\left(P-\vec{c}\right)^{-1}\right)\right) \cdot \vec{v}.$    

We want to show this is $ < 0$, so it suffices to show that

$\displaystyle \left(f\left(P-\left(\vec{c}+\varepsilon \vec{v}\right)\right) - f\left(P-\vec{c}\right)\right) \cdot \vec{v}$ $\displaystyle \leq 0$ (6)

and

$\displaystyle \left(f\left(\left(P-\left(\vec{c}+\varepsilon \vec{v}\right)\right)^{-1}\right) - f\left(\left(P-\vec{c}\right)^{-1}\right)\right) \cdot \vec{v}$ $\displaystyle > 0.$ (7)

Proof of (8):

Define

$\displaystyle \mathbb{S}_{\vec{v}}^+$ $\displaystyle = \left\{\vec{u}\in \mathbb{S}^{n-1} : \vec{u}\cdot \vec{v}> 0\right\}$    
$\displaystyle \mathbb{S}_{\vec{v}}^-$ $\displaystyle = \left\{\vec{u}\in \mathbb{S}^{n-1} : \vec{u}\cdot \vec{v}< 0\right\}.$    

For each $ \vec{u}\in \mathbb{S}_{\vec{v}}^+$, let $ \vec{u}^- = \vec{u}- 2\left(\vec{u}\cdot \vec{v}\right) \vec{v}\in \mathbb{S}_{\vec{v}}^-$; i.e. $ \vec{u}^-$ is $ \vec{u}$ with its ``$ \vec{v}$'' component reversed. Note that

$\displaystyle \vec{u}^- \cdot \vec{v}= - \, \vec{u}\cdot \vec{v}.$ (8)

Since the disjoint union $ \mathbb{S}_{\vec{v}}^+ \cup \mathbb{S}_{\vec{v}}^-$ is all of $ \mathbb{S}^{n-1}$ except for a set of area zero, we can pair up the terms in the definition of $ f\left(P-\vec{c}\right)$, as follows:

$\displaystyle f\left(P-\vec{c}\right)$ $\displaystyle = \int_{\vec{u}\in \mathbb{S}^{n-1}} \log\left(r_{P-\vec{c}}\left(\vec{u}\right)\right) \vec{u}\; dA, \;\;\;\;$   by definition of $ f$    
  $\displaystyle = \int_{\vec{u}\in \mathbb{S}_{\vec{v}}^+} \log\left(r_{P-\vec{c}...
...S}_{\vec{v}}^-} \log\left(r_{P-\vec{c}}\left(\vec{u}\right)\right) \vec{u}\; dA$    
  $\displaystyle = \int_{\vec{u}\in \mathbb{S}_{\vec{v}}^+} \left(\log\left(r_{P-\...
...u}+ \log\left(r_{P-\vec{c}}\left(\vec{u}^-\right)\right) \vec{u}^-\right) \; dA$    

So

$\displaystyle f\left(P-\vec{c}\right) \cdot \vec{v}=$ $\displaystyle \int_{\vec{u}\in \mathbb{S}_{\vec{v}}^+} \left(\log\left(r_{P-\ve...
...r_{P-\vec{c}}\left(\vec{u}^-\right)\right) \vec{u}^- \cdot \vec{v}\right) \; dA$    
$\displaystyle =$ $\displaystyle \int_{\vec{u}\in \mathbb{S}_{\vec{v}}^+} \left(\log\left(r_{P-\ve...
...P-\vec{c}}\left(\vec{u}^-\right)\right) \vec{u}\cdot \vec{v}\right) \; dA, \;\;$   by (11)    
$\displaystyle =$ $\displaystyle \int_{\vec{u}\in \mathbb{S}_{\vec{v}}^+} \left(\log\left(r_{P-\ve...
...eft(r_{P-\vec{c}}\left(\vec{u}^-\right)\right)\right) \vec{u}\cdot \vec{v}\; dA$    
$\displaystyle =$ $\displaystyle \int_{\vec{u}\in \mathbb{S}_{\vec{v}}^+} \log\left(\frac{r_{P-\ve...
...}\right)}{r_{P-\vec{c}}\left(\vec{u}^-\right)}\right) \vec{u}\cdot \vec{v}\; dA$    

Using this and the analogous expression for $ f\left(P-\left(\vec{c}+\varepsilon \vec{v}\right)\right) \cdot \vec{v}$, we get:

  $\displaystyle \left(f\left(P-\left(\vec{c}+\varepsilon \vec{v}\right)\right) - f\left(P-\vec{c}\right)\right) \cdot \vec{v}$    
$\displaystyle =$ $\displaystyle \int_{\vec{u}\in \mathbb{S}_{\vec{v}}^+} \left(\log\left(\frac{r_...
...)}{r_{P-\vec{c}}\left(\vec{u}^-\right)}\right)\right) \vec{u}\cdot \vec{v}\; dA$    

To show that this is $ \leq 0$, it suffices to show that the integrand is $ \leq 0$ for all $ \vec{u}\in \mathbb{S}_{\vec{v}}^+$. Each $ \vec{u}\cdot \vec{v}> 0$ by definition of $ \mathbb{S}_{\vec{v}}^+$, so we just need to show that

$\displaystyle \log\left(\frac{r_{P-\left(\vec{c}+\varepsilon \vec{v}\right)}\le...
...)}{r_{P-\left(\vec{c}+\varepsilon \vec{v}\right)}\left(\vec{u}^-\right)}\right)$ $\displaystyle - \log\left(\frac{r_{P-\vec{c}}\left(\vec{u}\right)}{r_{P-\vec{c}}\left(\vec{u}^-\right)}\right) \leq 0,$    

i.e. that

$\displaystyle \log\left(\frac{r_{P-\left(\vec{c}+\varepsilon \vec{v}\right)}\le...
...)}{r_{P-\left(\vec{c}+\varepsilon \vec{v}\right)}\left(\vec{u}^-\right)}\right)$ $\displaystyle \leq \log\left(\frac{r_{P-\vec{c}}\left(\vec{u}\right)}{r_{P-\vec{c}}\left(\vec{u}^-\right)}\right),$    

i.e. that

$\displaystyle \frac{r_{P-\left(\vec{c}+\varepsilon \vec{v}\right)}\left(\vec{u}\right)}{r_{P-\left(\vec{c}+\varepsilon \vec{v}\right)}\left(\vec{u}^-\right)}$ $\displaystyle \leq \frac{r_{P-\vec{c}}\left(\vec{u}\right)}{r_{P-\vec{c}}\left(\vec{u}^-\right)}.$ (9)

Figure 1: Slice of $ P$ showing that $ \frac{r_{P-\left(\vec {c}+\varepsilon \vec {v}\right)}\left(\vec {u}\right)}{r...
...rac{r_{P-\vec {c}}\left(\vec {u}\right)}{r_{P-\vec {c}}\left(\vec {u}^-\right)}$.
\begin{figure}\begin{center}
\setlength{\unitlength}{\textwidth / 20}%% (use ca...
...e\{1\}\}
% put(9,1)\{ circle\{1\}\}
\par\end{picture} \end{center} \end{figure}

Figure 1 shows the intersection of $ P$ with a 2-d plane containing $ \vec{c}$, $ \vec{c}+\vec{v}$, and  $ \vec{c}+\vec{u}$. The fact that $ \vec{u}\cdot \vec{v}> 0$ guarantees that the two outer lines, from $ \vec{c}$ to $ \mathit{bd}\left(P\right)$ in the direction of $ \vec{u}^-$ and from $ \vec{c}+\varepsilon \vec{v}$ to $ \mathit{bd}\left(P\right)$ in the direction of $ \vec{u}$, do not cross. The two inner lines may or may not cross. If the part of the boundary of $ P$ leading from $ \vec{c}+r_{P-\vec{c}}\left(\vec{u}^-\right)\vec{u}^-$ to $ \left(\vec{c}+\varepsilon \vec{v}\right) + r_{P-\left(\vec{c}+\varepsilon \vec{v}\right)}\left(\vec{u}\right)\vec{u}$ is a straight line, then by similar triangles (14) holds as equality; otherwise the denominator of the LHS and the numerator of the RHS (i.e. the lengths of the inner slanted lines in Figure 1) both become bigger, and so (14) still holds.

Proof of (10):

  $\displaystyle \left(f\left(\left(P-\left(\vec{c}+\varepsilon \vec{v}\right)\right)^{-1}\right) - f\left(\left(P-\vec{c}\right)^{-1}\right)\right) \cdot \vec{v}$    
$\displaystyle =$ $\displaystyle \int_{\vec{u}\in \mathbb{S}^{n-1}} \left(\log\left(r_{\left(P-\le...
...vec{c}\right)^{-1}}\left(\vec{u}\right)\right)\right) \vec{u}\cdot \vec{v}\; dA$    
$\displaystyle =$ $\displaystyle \int_{\vec{u}\in \mathbb{S}^{n-1}} \log\left(\frac{r_{\left(P-\le...
...ft(P-\vec{c}\right)^{-1}}\left(\vec{u}\right)}\right) \vec{u}\cdot \vec{v}\; dA$    
$\displaystyle =$ $\displaystyle \int_{\vec{u}\in \mathbb{S}^{n-1}} \log\left(\frac{\max_{\vec{p}\...
...\right)\right) \cdot \vec{u}\right)}\right) \vec{u}\cdot \vec{v}\; dA, \;\;\;\;$   by Corollary 2.1    
$\displaystyle =$ $\displaystyle \int_{\vec{u}\in \mathbb{S}^{n-1}} \log\left(\frac{\max_{\vec{p}\...
...{u}\right) - \varepsilon \vec{v}\cdot \vec{u}}\right) \vec{u}\cdot \vec{v}\; dA$ (10)

We want to show that this integral is $ > 0$. When $ \vec{u}\cdot \vec{v}> 0$, the (positive) denominator in (15) is $ <$ the (positive) numerator, so the logarithm is $ > 0$ and so the integrand is $ > 0$. Similarly, when $ \vec{u}\cdot \vec{v}< 0$, the logarithm is $ < 0$ and so again the integrand is $ > 0$. So the integrand of (15) is $ > 0$ for all $ \vec{u}$ for which $ \vec{u}\cdot \vec{v}\neq 0$, which is all of $ \mathbb{S}^{n-1}$ except for a set of area zero; therefore the integral is $ > 0$, as desired, and so (10) is established. This completes the proof of Lemma 3.4. $ \square$

Lemma 3.5   If $ P \in {\mathcal{P}^n}$, then there exists $ \vec{c}\in \mathit{int}\left(P\right)$ such that $ F_P\left(\vec{c}\right) = \vec{0}$.

Proof of Lemma 3.5: We can assume without loss of generality that the interior of $ P$ contains the origin (otherwise pick an arbitrary interior point of $ P$ and call it the origin); so $ P \in {\mathcal{P}^n_0}$. It seems clear that as $ \vec{c}\in \mathit{int}\left(P\right)$ approaches the boundary $ \mathit{bd}\left(P\right)$, $ F_P\left(\vec{c}\right) \!\cdot\! \left({\vec{c}}/{\left\Vert\vec{c}\right\Vert}\right)$ will decrease rapidly. So our strategy is to find $ \varepsilon > 0$ small enough so that for all $ \vec{b}\in \mathit{bd}\left(P\right)$, for all $ \vec{c}$ on the segment strictly between $ \vec{0}$ and $ \vec{b}$ with $ \left\Vert\vec{b}-\vec{c}\right\Vert \leq \varepsilon \, $,

$\displaystyle F_P\left(\vec{c}\right) \cdot \frac{\vec{c}}{\left\Vert\vec{c}\right\Vert} \leq 0;$    

then we will be able to apply Lemma A.2 (see Appendix) using the function $ -F_P$ on a slightly shrunken $ P$, with the amount of shrinkage based on $ \varepsilon$.

We will need to do some calculations in order to see how small we need to make $ \varepsilon$.

Let $ \theta = \tan^{-1}\left(\frac{r_{\min}\left(P\right)}
{r_{\max}\left(P\right)}\right) \in \left(0,\frac{\pi}{4}\right)$, where $ r_{\min}\left(P\right), r_{\max}\left(P\right)$ are respectively the min and max distances from the origin to $ \mathit{bd}\left(P\right)$.

For all $ \vec{v}\in \mathbb{S}^{n-1}$, define

$\displaystyle \mathbb{D}_{\,\theta}\!\left(\vec{v}\right) = \left\{\vec{u}\in \mathbb{S}^{n-1} : \mathit{angle}\left(\vec{u},\vec{v}\right) \leq \theta\right\}.$    

That is, $ \mathbb{D}_{\,\theta}\left(\vec{v}\right)$ is the closed (hyper-) spherical disk of radius $ \theta$ centered at $ \vec{v}$.

Figure 2: Pie and ice cream.
\begin{figure}\begin{center}
\setlength{\unitlength}{\textwidth / 22}%% (use ca...
...akebox(0,0)[b]{$\vec{v}$}}
\par\thinlines\end{picture} \end{center} \end{figure}

Let $ \vec{b}$ be an arbitrary boundary point of P, and $ \vec{v}$ = $ {\vec{b}}/{\left\Vert\vec{b}\right\Vert}$, so $ \vec{b}$ = $ r_P\left(\vec{v}\right)\vec{v}$.

Note that for all $ \vec{c}\in \left[\vec{0},\vec{b}\right)$, for all $ \vec{u}\in \mathbb{D}_{\,\theta}\left(- \vec{v}\right)$,

$\displaystyle r_{P-\vec{c}}\left(\vec{u}\right) \geq r_{\min}\left(P\right).$ (11)

This can be seen geometrically (see Figure 2) since, for such $ \vec{c}$, the pie-slice-shaped set

$\displaystyle \{\vec{c}+ t\,r_{\min}\left(P\right) \vec{u}:$    $ \vec{u}\in \mathbb{D}_{\,\theta}\left(- \vec{v}\right)$ and $ 0 \leq t \leq 1$$\displaystyle \}$    

is a subset of the ice-cream-cone-shaped convex hull of

$\displaystyle \{\vec{z}\in \mathbb{R}^n :$    $ \left\Vert\vec{z}\right\Vert \leq r_{\min}\left(P\right)$ and $ \vec{z}\cdot \vec{v}\leq 0$$\displaystyle \} \cup \{\vec{b}\}$    

which is a subset of $ P$. ($ \theta$ was chosen to be small enough so that this would work for all $ \vec{b}$ on the boundary of $ P$).

For each $ \vec{u}\in \mathbb{D}_{\,\theta}\left(\vec{v}\right)$, define $ \vec{u}' = 2\left(\vec{u}\cdot \vec{v}\right)\vec{v}- \vec{u}$; i.e. $ \vec{u}'$ is $ \vec{u}$ reflected across $ \vec{v}$. Then $ \vec{u}' \in \mathbb{D}_{\,\theta}\left(\vec{v}\right)$, and

$\displaystyle \vec{u}' \cdot \vec{v}= \vec{u}\cdot \vec{v}.$ (12)

Define $ \mathcal{H}_{\vec{b}} = \left\{\vec{z}\in \mathbb{R}^n : \vec{z}\cdot \vec{v}\leq \vec{b}\cdot \vec{v}\right\}$.

Then for any $ \vec{c}$ strictly between $ \vec{0}$ and $ \vec{b}$, $ \vec{c}+ r_{P-\vec{c}}\left(\vec{v}\right)\vec{v}= \vec{b}$ is on the boundary of the closed halfspace $ \mathcal{H}_{\vec{b}}$, so by convexity of $ P$, for each $ \vec{u}\in \mathbb{D}_{\,\theta}\left(\vec{v}\right)$, at least one of $ P$'s boundary points $ \vec{c}+ r_{P-\vec{c}}\left(\vec{u}\right)\vec{u}$ and  $ \vec{c}+ r_{P-\vec{c}}\left(\vec{u}'\right)\vec{u}'$ is in $ \mathcal{H}_{\vec{b}}$. [XXX picture would be nice] I.e.

$\displaystyle \left(\vec{c}+ r_{P-\vec{c}}\left(\vec{u}\right)\vec{u}\right) \cdot \vec{v}\leq \vec{b}\cdot \vec{v}\;\;\;\;$    or $\displaystyle \;\;\;\; \left(\vec{c}+ r_{P-\vec{c}}\left(\vec{u}'\right)\vec{u}'\right) \cdot \vec{v}\leq \vec{b}\cdot \vec{v}$    

i.e.

$\displaystyle r_{P-\vec{c}}\left(\vec{u}\right)\vec{u}\leq \frac{\left(\vec{b}-\vec{c}\right) \cdot \vec{v}}{\vec{u}\cdot \vec{v}} \;\;\;\;$    or $\displaystyle \;\;\;\; r_{P-\vec{c}}\left(\vec{u}'\right)\vec{u}' \leq \frac{\left(\vec{b}-\vec{c}\right) \cdot \vec{v}}{\vec{u}' \cdot \vec{v}}$    

(since $ \vec{u}\cdot \vec{v}> 0$ and  $ \vec{u}' \cdot \vec{v}> 0$, since $ \vec{u},\vec{u}' \in \mathbb{D}_{\,\theta}\left(\vec{v}\right)$). I.e., by (17),

$\displaystyle \min\left(r_{P-\vec{c}}\left(\vec{u}\right)\vec{u}, r_{P-\vec{c}}\left(\vec{u}'\right)\vec{u}'\right)$ $\displaystyle \leq \frac{\left(\vec{b}-\vec{c}\right) \cdot \vec{v}}{\vec{u}\cdot \vec{v}}$    
  $\displaystyle = \frac{\left\Vert\vec{b}-\vec{c}\right\Vert}{\vec{u}\cdot \vec{v}}.$ (13)

But for $ \vec{u}\in \mathbb{D}_{\,\theta}\left(\vec{v}\right)$, we know that

$\displaystyle 0 \leq \mathit{angle}\left(\vec{u},\vec{v}\right) \leq \theta \leq \frac{\pi}{4}, \nonumber$    

so, since the cosine function is decreasing on the interval $ \left[0,{\pi}/{4}\right]$,

$\displaystyle \vec{u}\cdot \vec{v}= \cos\left(\mathit{angle}\left(\vec{u},\vec{v}\right)\right)$ $\displaystyle \geq \cos\left(\frac{\pi}{4}\right)$    
  $\displaystyle = \frac{1}{\sqrt{2}}.$    

Applying this to (18), we get, for $ \vec{u}\in \mathbb{D}_{\,\theta}\left(\vec{v}\right)$:

$\displaystyle \min\left(r_{P-\vec{c}}\left(\vec{u}\right)\vec{u}, r_{P-\vec{c}}...
...c{u}'\right)\vec{u}'\right) \leq \sqrt{2} \left\Vert\vec{b}-\vec{c}\right\Vert.$ (14)

Let's look at the contributions the disjoint sets $ \mathbb{D}_{\,\theta}\left(\vec{v}\right)$, $ \mathbb{D}_{\,\theta}\left(- \vec{v}\right)$, and  $ \mathbb{S}^{n-1}\setminus \mathbb{D}_{\,\theta}\left(\vec{v}\right) \setminus \mathbb{D}_{\,\theta}\left(- \vec{v}\right)$ make to $ f\left(P-\vec{c}\right) \cdot \vec{v}$ when $ \vec{c}\in \mathit{int}\left(P\right)$ lies on the segment $ \left(\vec{0}, \vec{b}\right)$ and  $ \left\Vert\vec{b}-\vec{c}\right\Vert \leq r_{\min}\left(P\right)$.

[XXX In all three of the following computations, I think we can avoid the $ \vec {u}\cdot \vec {v}\leq \left\Vert\vec {u}\right\Vert \left\Vert\vec {v}\right\Vert$ step, so that we end up with a bunch of integrals of $ \vec {u}\cdot \vec {v}$ in (24) so that it becomes more uniform as well as a tighter bound. If we care.]

For such $ \vec{c}$, the contribution that $ \mathbb{D}_{\,\theta}\left(\vec{v}\right)$ makes to $ f\left(P-\vec{c}\right) \cdot \vec{v}$ is:

  $\displaystyle \int_{\vec{u}\in \mathbb{D}_{\,\theta}\left(\vec{v}\right)} \log\left(r_{P-\vec{c}}\left(\vec{u}\right)\right) \vec{u}\cdot \vec{v}\; dA$    
$\displaystyle =$ $\displaystyle \frac{1}{2} \left( \int_{\vec{u}\in \mathbb{D}_{\,\theta}\left(\v...
...left(r_{P-\vec{c}}\left(\vec{u}\right)\right) \vec{u}\cdot \vec{v}\; dA \right)$    
$\displaystyle =$ $\displaystyle \frac{1}{2} \left( \int_{\vec{u}\in \mathbb{D}_{\,\theta}\left(\v...
...t(r_{P-\vec{c}}\left(\vec{u}'\right)\right) \vec{u}' \cdot \vec{v}\; dA \right)$    
$\displaystyle <tex2html_comment_mark>179 =$ $\displaystyle \frac{1}{2} \left( \int_{\vec{u}\in \mathbb{D}_{\,\theta}\left(\v...
...ft(r_{P-\vec{c}}\left(\vec{u}'\right)\right) \vec{u}\cdot \vec{v}\; dA \right),$    
  $\displaystyle \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $   since $ \left(\vec{u}' \in \mathbb{D}_{\,\theta}\left(\vec{v}\right) \Leftrightarrow \vec{u}\in \mathbb{D}_{\,\theta}\left(\vec{v}\right)\right)$ and  $ \vec{u}' \cdot \vec{v}= \vec{u}\cdot \vec{v}$    
$\displaystyle <tex2html_comment_mark>181 =$ $\displaystyle \frac{1}{2} \int_{\vec{u}\in \mathbb{D}_{\,\theta}\left(\vec{v}\r...
...eft(r_{P-\vec{c}}\left(\vec{u}'\right)\right) \right) \vec{u}\cdot \vec{v}\; dA$    
$\displaystyle =$ $\displaystyle \frac{1}{2} \int_{\vec{u}\in \mathbb{D}_{\,\theta}\left(\vec{v}\r...
...}\left(\vec{u}\right), r_{P-\vec{c}}\left(\vec{u}'\right)\right)\right) \right.$    
$\displaystyle %% XXX gross spacing hack. there has GOT to be a better way to do this!
$ $\displaystyle \ \ \ \ \ \ \ \ \ \ \ \ \ \: \left. + \log\left( \max\left( r_{P-...
...P-\vec{c}}\left(\vec{u}'\right)\right)\right) \right) \vec{u}\cdot \vec{v}\; dA$    
  [XXX separate next step into two steps. Also I think maybe $ \mathit{diam}(P)$ can be replaced with $ r_{\max}(P)$]    
$\displaystyle \leq$ $\displaystyle \frac{1}{2} \int_{\vec{u}\in \mathbb{D}_{\,\theta}\left(\vec{v}\r...
...ght)\right) \right) \vec{u}\cdot \vec{v}\; dA <tex2html_comment_mark>183 \;\;\;$   by (19) and  $ \vec{u}\cdot \vec{v}> 0$    
$\displaystyle =$ $\displaystyle \frac{1}{2} \left( \log\left(\sqrt{2} \left\Vert\vec{b}-\vec{c}\r...
...\vec{u}\in \mathbb{D}_{\,\theta}\left(\vec{v}\right)} \vec{u}\cdot \vec{v}\; dA$    
$\displaystyle =$ $\displaystyle \frac{1}{2} \left( \log\left( \left\Vert\vec{b}-\vec{c}\right\Ver...
...\vec{u}\in \mathbb{D}_{\,\theta}\left(\vec{v}\right)} \vec{u}\cdot \vec{v}\; dA$    
$\displaystyle =$ $\displaystyle \frac{1}{2} \log\left\Vert\vec{b}-\vec{c}\right\Vert \int_{\vec{u...
...\vec{u}\in \mathbb{D}_{\,\theta}\left(\vec{v}\right)} \vec{u}\cdot \vec{v}\; dA$    
$\displaystyle \leq$ $\displaystyle \frac{1}{2} \log\left\Vert\vec{b}-\vec{c}\right\Vert \int_{\vec{u...
...\vec{v}\right)} \left\Vert\vec{u}\right\Vert \left\Vert\vec{v}\right\Vert \; dA$    
$\displaystyle =$ $\displaystyle \frac{1}{2} \log\left\Vert\vec{b}-\vec{c}\right\Vert \int_{\vec{u...
...) \right\vert \int_{\vec{u}\in \mathbb{D}_{\,\theta}\left(\vec{v}\right)} \! dA$    
  $\displaystyle \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $   since $ \vec{u},\vec{v}$ are unit vectors    
$\displaystyle =$ $\displaystyle \frac{1}{2} \log\left\Vert\vec{b}-\vec{c}\right\Vert \int_{\vec{u...
...\right\vert \mathit{Area}\left(\mathbb{D}_{\,\theta}\left(\vec{v}\right)\right)$ (15)

where $ \mathit{diam}(P) = \max \left\{\left\Vert\vec{p_1}- \vec{p_0}\right\Vert : \vec{p_0}, \vec{p_1}\in P\right\}$ exists and is finite by compactness of P.

The contribution that $ \mathbb{D}_{\,\theta}\left(- \vec{v}\right)$ makes to $ f\left(P-\vec{c}\right) \cdot \vec{v}$ is:

  $\displaystyle \int_{\vec{u}\in \mathbb{D}_{\,\theta}\left(- \vec{v}\right)} \log\left(r_{P-\vec{c}}\left(\vec{u}\right)\right) \vec{u}\cdot \vec{v}\; dA$    
$\displaystyle \leq$ $\displaystyle \int_{\vec{u}\in \mathbb{D}_{\,\theta}\left(- \vec{v}\right)} \log\left(r_{\min}\left(P\right)\right) \vec{u}\cdot \vec{v}\; dA \;\;\;\;$   by (16) and $ \vec{u}\cdot \vec{v}< 0$    
$\displaystyle =$ $\displaystyle \log\left(r_{\min}\left(P\right)\right) \int_{\vec{u}\in \mathbb{D}_{\,\theta}\left(- \vec{v}\right)} \vec{u}\cdot \vec{v}\; dA$    
$\displaystyle \leq$ $\displaystyle \left\vert\log r_{\min}\left(P\right)\right\vert \int_{\vec{u}\in...
...ec{v}\right)} \left\Vert \vec{u}\right\Vert \left\Vert \vec{v}\right\Vert \; dA$    
$\displaystyle =$ $\displaystyle \left\vert\log r_{\min}\left(P\right)\right\vert \int_{\vec{u}\in \mathbb{D}_{\,\theta}\left(- \vec{v}\right)} \! dA \;\;\;\;$   since $ \vec{u},\vec{v}$ are unit vectors    
$\displaystyle =$ $\displaystyle \left\vert\log r_{\min}\left(P\right)\right\vert \mathit{Area}\!\left(\mathbb{D}_{\,\theta}\left(- \vec{v}\right)\right).$ (16)

And the contribution that $ \mathbb{S}^{n-1}\setminus \mathbb{D}_{\,\theta}\left(\vec{v}\right) \setminus \mathbb{D}_{\,\theta}\left(- \vec{v}\right)$ makes to $ f\left(P-\vec{c}\right) \cdot \vec{v}$ is:

  $\displaystyle \int_{\vec{u}\in \mathbb{S}^{n-1}\setminus \mathbb{D}_{\,\theta}\...
...)} \log\left(r_{P-\vec{c}}\left(\vec{u}\right)\right) \vec{u}\cdot \vec{v}\; dA$    
$\displaystyle \leq$ $\displaystyle \int_{\vec{u}\in \mathbb{S}^{n-1}\setminus \mathbb{D}_{\,\theta}\...
...}\right)} \log\left(r_{P}\left(\vec{u}\right)\right) \vec{u}\cdot \vec{v}\; dA,$    

by the same pairing argument as the proof of (8) in Lemma 3.4, since $ \vec{c}$ is in direction $ \vec{v}$ from $ \vec{0}$

$\displaystyle \leq$ $\displaystyle \int_{\vec{u}\in \mathbb{S}^{n-1}\setminus \mathbb{D}_{\,\theta}\...
...ht)\right\vert \left\Vert\vec{u}\right\Vert \left\Vert \vec{v}\right\Vert \; dA$    
$\displaystyle =$ $\displaystyle \int_{\vec{u}\in \mathbb{S}^{n-1}\setminus \mathbb{D}_{\,\theta}\...
...c{v}\right)} \left\vert\log r_{P}\left(\vec{u}\right)\right\vert \; dA \;\;\;\;$   since $ u,v$ are unit vectors    
$\displaystyle \leq$ $\displaystyle \int_{\vec{u}\in \mathbb{S}^{n-1}\setminus \mathbb{D}_{\,\theta}\...
...ight)\right\vert, \left\vert\log r_{\max}\left(P\right)\right\vert\right) \; dA$    
$\displaystyle =$ $\displaystyle \max\left(\left\vert\log r_{\min}\left(P\right)\right\vert, \left...
...}\left(\vec{v}\right) \setminus \mathbb{D}_{\,\theta}\left(- \vec{v}\right)} dA$    
$\displaystyle =$ $\displaystyle \max\left(\left\vert\log r_{\min}\left(P\right)\right\vert, \left...
...ft(\vec{v}\right) \setminus \mathbb{D}_{\,\theta}\left(- \vec{v}\right)\right).$ (17)

Putting it all together, we get:

  $\displaystyle F\left(P-\vec{c}\right) \cdot \vec{v}$    
$\displaystyle =$ $\displaystyle f\left(P-\vec{c}\right) \cdot \vec{v}- f\left(\left(P-\vec{c}\right)^{-1}\right) \cdot \vec{v}\;\;\;\;$   by definition of $ F$    
$\displaystyle \leq$ $\displaystyle f\left(P-\vec{c}\right) \cdot \vec{v}- f\left({P^{-1}}\right) \cdot \vec{v}\;\;\;\;$   by (10) in proof of Lemma 3.4,    
  $\displaystyle \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $   since $ \vec{c}$ is in direction $ \vec{v}$ from $ \vec{0}$    
$\displaystyle \leq$ $\displaystyle f\left(P-\vec{c}\right) \cdot \vec{v}+ \left\Vert f\left({P^{-1}}\right)\right\Vert \left\Vert\vec{v}\right\Vert$    
$\displaystyle =$ $\displaystyle f\left(P-\vec{c}\right) \cdot \vec{v}+ \left\Vert f\left({P^{-1}}\right)\right\Vert$    
$\displaystyle =$ $\displaystyle \int_{\vec{u}\in \mathbb{S}^{n-1}} \log\left(r_{P-\vec{c}}\left(\...
...}\cdot \vec{v}\; dA \;+\; \left\Vert f\left({P^{-1}}\right)\right\Vert \;\;\;\;$   by definition of $ f$    
$\displaystyle =$ $\displaystyle \left( \int_{\vec{u}\in \mathbb{D}_{\,\theta}\left(\vec{v}\right)...
...t) \log\left(r_{P-\vec{c}}\left(\vec{u}\right)\right) \vec{u}\cdot \vec{v}\; dA$    
  $\displaystyle + \left\Vert f\left({P^{-1}}\right)\right\Vert$    
$\displaystyle \leq\;$ $\displaystyle \frac{1}{2} \log \left\Vert\vec{b}-\vec{c}\right\Vert \int_{\vec{...
...\right\vert \mathit{Area}\left(\mathbb{D}_{\,\theta}\left(\vec{v}\right)\right)$    
  $\displaystyle + \left\vert\log r_{\min}\left(P\right)\right\vert \mathit{Area}\!\left(\mathbb{D}_{\,\theta}\left(- \vec{v}\right)\right)$    
  $\displaystyle + \max\left(\left\vert\log r_{\min}\left(P\right)\right\vert, \le...
...eft(\vec{v}\right) \setminus \mathbb{D}_{\,\theta}\left(- \vec{v}\right)\right)$    
  $\displaystyle + \left\Vert f\left({P^{-1}}\right)\right\Vert$ (18)

by (20), (21), and (23).

Notice that neither the integral nor the areas appearing in (24) depend on $ \vec{v}$ at all; they are the same for all $ \vec{v}$, depending only on $ \theta$ which is a constant (depending on $ P$). So the only part of (24) that is not constant is $ \left\Vert\vec{b}-\vec{c}\right\Vert$, and so we can rewrite (24) as:

$\displaystyle F\left(P-\vec{c}\right) \cdot \vec{v}\leq \log \left\Vert\vec{b}-\vec{c}\right\Vert \; C_1 + C_2$ (19)

for appropriate constants $ C_1$, $ C_2$ (depending on $ P$). Note that $ C_1 > 0$, so we can make the RHS of (25) less than any desired target by choosing sufficiently small $ \varepsilon > 0$ and requiring $ \left\Vert\vec{b}-\vec{c}\right\Vert \leq \varepsilon$; then the LHS $ F\left(P-\vec{c}\right) \cdot \vec{v}$ will be less than the desired target as well.

Now we are finally ready to show that $ \vec{0}\in \mathit{range}\left(F_P\right)$. By the previous paragraph (setting our ``desired target'' to be 0), choose $ \varepsilon \in \left(0, {r_{\min}\left(P\right) / 2}\right)$ small enough so that for all $ \vec{b}\in bd\left(P\right)$ and $ \vec{c}$ strictly between $ \vec{0}$ and $ \vec{b}$ with $ \left\Vert\vec{b}-\vec{c}\right\Vert \leq \varepsilon$,

$\displaystyle F\left(P-\vec{c}\right) \cdot \vec{v}$ $\displaystyle \leq 0$    

where $ \vec{v}= {\vec{b}} / {\left\Vert\vec{b}\right\Vert}
= {\vec{c}} / {\left\Vert\vec{c}\right\Vert}$; i.e.

$\displaystyle F\left(P-\vec{c}\right) \cdot \vec{c}$ $\displaystyle \leq 0$    
$\displaystyle F_P\left(\vec{c}\right) \cdot \vec{c}$ $\displaystyle \leq 0.$ (20)

Define $ P_\varepsilon = \left\{\vec{0}\right\} \cup \left\{\vec{c}\in \mathit{int}\lef...
...\left\Vert\vec{c}\right\Vert \leq r_P\left(\vec{c}\right) - \varepsilon\right\}$; i.e. $ P_\varepsilon$ is $ P$ with its boundary shrunk by $ \varepsilon$ units radially towards the origin. Then $ bd\left(P_\varepsilon\right) = \left\{\vec{c}\in \mathit{int}\left(P\right) : \left\Vert\vec{c}\right\Vert = r_P\left(\vec{c}\right) - \varepsilon\right\}$, so all points $ \vec{c}\in \mathit{bd}\left(P_\varepsilon\right)$ satisfy (27). $ P_\varepsilon$ is not necessarily in $ {\mathcal{P}^n_0}$ since it typically is not convex[XXX picture might be nice]; however its convex hull $ \mathit{hull}\left(P_\varepsilon\right) \in {\mathcal{P}^n_0}$, and  $ P_\varepsilon \subset \mathit{hull}\left(P_\varepsilon\right) \subset \mathit{int}\left(P\right)$ (the latter inclusion being since $ P_\varepsilon \subset \mathit{int}\left(P\right)$ and  $ \mathit{int}\left(P\right)$ is convex). Then $ \mathit{bd}\left(\mathit{hull}\left(P_\varepsilon\right)\right)$ is even closer to $ \mathit{bd}\left(P\right)$ than $ \mathit{bd}\left(P_\varepsilon\right)$ is, so all points $ \vec{c}\in \mathit{bd}\left(\mathit{hull}\left(P_\varepsilon\right)\right)$ satisfy (27) as well. So the function $ -F_P$ restricted to $ \mathit{hull}\left(P_\varepsilon\right)$ satisfies the hypotheses of Lemma A.2 (see Appendix), so by that Lemma there exists $ \vec{c}\in \mathit{hull}\left(P_\varepsilon\right) \subset \mathit{int}(P)$ such that $ -F_P\left(\vec{c}\right) = \vec{0}$, and so $ F_P\left(\vec{c}\right) = \vec{0}$. $ \square$

Exercise 1   If $ P \in {\mathcal{P}^n}$, show that $ \mathit{range}\left(F_P\right) = \mathbb{R}^n$.

Definition: If $ P \in {\mathcal{P}^n}$, define $ \vec{c}\left(P\right)$ to be the unique point $ \vec{c}\in \mathit{int}\left(P\right)$ such that $ F\left(P - \vec{c}\right) = \vec{0}$; i.e. such that $ F_P\left(\vec{c}\right) = \vec{0}$. Existence and uniqueness of $ \vec{c}\left(P\right)$ is guaranteed by Lemmas 3.5 and 3.4 respectively.

Theorem 1   If $ P \in {\mathcal{P}^n}$ and $ \vec{c}= \vec{c}\left(P\right)$, then for any $ r > 0$, $ \vec{c}= \vec{c}\left(\mathit{reciprocal}\left(P,\vec{c},r\right)\right)$.

[ XXX in other words, $ \vec {c}: {\mathcal{P}^n}\rightarrow \mathbb{R}^n$ is a canonical reciprocation function, if we define that earlier]

Proof of Theorem 1:

Assuming $ F\left(P - \vec{c}\right) = \vec{0}$, we must show $ F\left(\mathit{reciprocal}\left(P,\vec{c},r\right)-\vec{c}\right) = \vec{0}$.

$\displaystyle F\left(\mathit{reciprocal}\left(P,\vec{c},r\right)-\vec{c}\right)$ $\displaystyle = F\left(r^2 \left(P-\vec{c}\right)^{-1}\right) \;\;\;\;$   by (7)$\displaystyle \nonumber$    
  $\displaystyle = F\left(\left(P-\vec{c}\right)^{-1}\right), \;\;\;\;$   by Lemma 3.2$\displaystyle \nonumber$    
  $\displaystyle = -F\left(P-\vec{c}\right), \;\;\;\;$   by Lemma 3.3$\displaystyle \nonumber$    
  $\displaystyle = -\vec{0}\;\;\;\;$   by assumption$\displaystyle \nonumber$    
  $\displaystyle = \vec{0}. \;\; \square \nonumber$    

Canonical Reciprocation Radius

[ XXX mention possible choices and relationships with the choice of canonical center ]

Open Problems

[ XXX closed formula? algorithm? ]

[ XXX other similar log-based definitions I've thought of and haven't disproved?]

[ XXX other definitions based on matching the primal and dual CG, for some notion of CG? ]

[ XXX a definition that is the centroid when P is a triangle? (or simplex)]

[ XXX characterize all canonical-reciprocation-center functions. what does the space of all such functions look like? Does it have isolated points? ]

[ XXX algebra of them? e.g. can we linearly interpolate between any two of them? ]

Conclusions

[ XXX write me]

Appendix

This appendix proves two topological lemmas related to Brower's fixed-point theorem. Lemma A.2 was used in the proof of Lemma 3.5.

Definitions: For $ n \geq 1$, let $ \mathbb{B}^n$ be the closed unit ball in $ \mathbb{R}^n$, and let $ \mathbb{S}^{n-1}$ be its boundary. That is,

$\displaystyle \mathbb{B}^n$ $\displaystyle = \left\{\vec{v}\in \mathbb{R}^n : \left\Vert\vec{v}\right\Vert \leq 1\right\} \nonumber$    
$\displaystyle \mathbb{S}^{n-1}$ $\displaystyle = \left\{\vec{u}\in \mathbb{R}^n : \left\Vert\vec{u}\right\Vert = 1\right\} \nonumber$    

Lemma A.1   If $ f : \mathbb{B}^n \rightarrow \mathbb{R}^n$ is continuous and  $ f\left(\vec{u}\right) \cdot \vec{u}\geq 0$ for all $ \vec{u}\in \mathbb{S}^{n-1}$, then $ \exists \vec{v}\!\in\! \mathbb{B}^n \; f\left(\vec{v}\right) = \vec{0}$.

Proof of Lemma A.1: Assume, to the contrary, that the origin is not in the range of $ f$. Then we can define a continuous function $ g: \mathbb{B}^n \rightarrow \mathbb{S}^{n-1}$ by:

$\displaystyle g\left(\vec{v}\right) = -\frac{f\left(\vec{v}\right)}{\left\Vert f\left(\vec{v}\right)\right\Vert}.$    

$ g$ is a continuous mapping from $ \mathbb{B}^n$ to $ \mathbb{B}^n$. Brower's fixed point theorem states that any such mapping must have a fixed point, so there exists $ \vec{u}\in \mathbb{B}^n$ such that $ \vec{u}= g\left(\vec{u}\right)$ (and so $ \vec{u}\in \mathbb{S}^{n-1}$). So

$\displaystyle \vec{u}$ $\displaystyle = g\left(\vec{u}\right) = -\frac{f\left(\vec{u}\right)}{\left\Vert f\left(\vec{u}\right)\right\Vert} \nonumber$    
$\displaystyle f\left(\vec{u}\right)$ $\displaystyle = -\left\Vert f\left(\vec{u}\right)\right\Vert \vec{u}. \nonumber$    

But then

$\displaystyle f\left(\vec{u}\right) \cdot \vec{u}$ $\displaystyle = \left(-\left\Vert f\left(\vec{u}\right)\right\Vert \vec{u}\right) \cdot \vec{u}\nonumber$    
  $\displaystyle = -\left\Vert f\left(\vec{u}\right)\right\Vert \left(\vec{u}\cdot \vec{u}\right) \nonumber$    
  $\displaystyle = -\left\Vert f\left(\vec{u}\right)\right\Vert \nonumber$    
  $\displaystyle < 0, \;\;\;\;$   since $ \vec{0}\not\in \mathit{range}\left(f\right)$$\displaystyle \nonumber$    

which contradicts the assumption that $ f\left(\vec{u}\right) \cdot \vec{u}\geq 0$ for all $ \vec{u}\in \mathbb{S}^{n-1}$. $ \square$

Lemma A.2   If $ P \in {\mathcal{P}^n_0}$ (that is, $ P$ is a compact convex subset of $ \mathbb{R}^n$ containing $ \vec{0}$ in its interior), and  $ f : P \rightarrow \mathbb{R}^n$ is a continuous function such that $ f\left(\vec{v}\right) \cdot \vec{v}\geq 0$ for all $ \vec{v}$ on the boundary of $ P$, then $ \exists \vec{v}\!\in\! P \; f\left(\vec{v}\right) = \vec{0}$.

Proof of Lemma A.2: The idea is to simply squash and stretch $ P$ radially from the origin so that it becomes the unit ball, and then apply Lemma A.1. Define a homeomorphism $ h : \mathbb{B}^n \rightarrow P$ by:

$\displaystyle h\left(\vec{0}\right)$ $\displaystyle = \vec{0}\nonumber$    
$\displaystyle h\left(\vec{v}\right)$ $\displaystyle = r_P\left(\vec{v}\right) \vec{v}, \;\;\;\; \vec{v}\neq \vec{0}\nonumber$    

where $ r_P\left(\vec{v}\right)$ is the distance from the origin to the boundary of $ P$ in the direction of $ \vec{v}$. Then the composite function $ f \!\circ\! h : \mathbb{B}^n \rightarrow \mathbb{R}^n$ is continuous, and for all $ \vec{u}\in \mathbb{S}^{n-1}$,

$\displaystyle f \!\circ\! h \left(\vec{u}\right) \cdot \vec{u}$ $\displaystyle = f\left(h\left(\vec{u}\right)\right) \cdot \vec{u}\nonumber$    
  $\displaystyle = f\left(r_P\left(\vec{u}\right)\vec{u}\right) \cdot \vec{u}\nonumber$    
  $\displaystyle = f\left(r_P\left(\vec{u}\right)\vec{u}\right) \cdot \left(r_P\left(\vec{u}\right) \vec{u}\right) / r_P\left(\vec{u}\right) \nonumber$    
  $\displaystyle \geq 0, \;\;\;\;$   since $ r_P\left(\vec{u}\right)\vec{u}$ is on the boundary of $ P$.$\displaystyle \nonumber$    

So $ f \!\circ\! h$ satisfies the conditions of Lemma A.1, so the origin is in the range of $ f \!\circ\! h$ and therefore is in the range of $ f$. $ \square$

Bibliography

1
John Conway. Personal communication, September 17 2002.

About this document ...

A Canonical Reciprocation Center
For Convex Objects

This document was generated using the LaTeX2HTML translator Version 2002 (1.62)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -html_version 3.2 -split 0 -math -image_type gif -transparent -no_reuse -no_navigation CanonicalReciprocationCenter.latex

The translation was initiated by on 2003-07-01


2003-07-01