0
$\begingroup$

In Jiri Matousek's book - "Lectures on Discrete Geometry", he defines centerpoint as:

1.4.1 Definition (Centerpoint). Let $X$ be an $n$-point set in $\mathbb R^d$. A point $x \in \mathbb R^d$ is called a centerpoint if each closed half-space containing $x$ contains at least $\frac{n}{d+1}$ points of $X$.

However, after some explanation, when he goes on to prove the Centerpoint Theorem, he says this:

First we note an equivalent definition of centerpoint:
$x$ is a centerpoint of $X$ if and only if it lies in each open half-space $\gamma$ such that $|X \cap \gamma| > \frac{d}{d+1}n$.

Can anyone explain to me how these two are definitions equivalent? Also, why does $\frac{n}{d+1}$ change to $\frac{nd}{d+1}$, when the characterization of half-spaces changes from closed to open?

Also, is there any significance of why in the first definition, only if is used, and in the second (alternate) definition if and only if is used? Does it mean that $\leftarrow$ side of first definition is not true?

$\endgroup$

1 Answer 1

2
+50
$\begingroup$

First of all, when making a definition if and if, and only if are often used interchangeably.

For the rest of the question, let D1 be the first definition, and let D2 be the second one.

Let $x\in\mathbb{R}^d$ satisfy D1. Take an open half-space $\gamma$ such that $|X\cap\gamma| > \tfrac{dn}{d+1}$. Then the complement $\gamma^c$ is closed and contains at most $n - \tfrac{dn}{d+1} = \frac{n}{d+1}$ points, and thus cannot contain $x$. It follows that $x\in\gamma$, so that $x$ satisfies D2.

Conversely, if $x\in\mathbb{R}^d$ satisfies D2, let $\delta$ be a closed half-space containing $x$. Its complement $\delta^c$ is open and doesn't contain $x$, and thus we have $|X\cap\delta^c|\le \tfrac{dn}{d+1}$, so that $\delta$ must contain at least $\tfrac{n}{d+1}$ points of $X$. Therefore, $x$ satisfies D1.

As it is now evident from the proof of the equivalence, the switch between $\tfrac{n}{d+1}$ and $\tfrac{dn}{d+1}$ is given by taking the complement.

$\endgroup$
1
  • $\begingroup$ Thanks, I understand now. :-) $\endgroup$
    – taninamdar
    Commented Nov 4, 2015 at 18:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .