0
$\begingroup$

Let $\mathcal{P}$ a finite set of points of a Euclidean $\mathbb{E}^n$ and take the union $\mathrm{U}(\mathcal{P})$ of all closed half-spaces defined by $n$ elements of $\mathcal{P}$ that contain only points of the convex hull $\mathrm{CH}(\mathcal{P})$ of $\mathcal{P}$

Questions:

  • is there an established name and/or notation for the closed complement of $\mathrm{U}(\mathcal{P})$?
  • how can the closed complement of $\mathrm{U}(\mathcal{P})$ be calculated efficiently?
  • has the closed complement of $\mathrm{U}(\mathcal{P})$ already been encountered e.g. in computational geometry or statistical sampling?

I am tempted to call $\mathrm{CH}(\mathcal{P})$ detached from $\mathcal{P}$ if the convex hull of closed complement of $\mathrm{U}(\mathcal{P})$ is a proper subset of $\mathrm{CH}(\mathcal{P})$ and attached otherwise.

edit:
an equivalent, but simpler definition for the closed complement of $\mathrm{U}(\mathcal{P})$ is:

"the intersection of all closed half-spaces that contain all inner points and at least $n$ points of $\mathrm{CH}(\mathcal{P})$".

Illustration: enter image description here attached vs detached hull

in case of a detached convex hull there exists a hyperplane through $n$ points of $\mathcal{P}$ on the convex hull that cuts off an empty inner portion of the convex region defined b $\mathrm{CH}(\mathcal{P})$, whereas in the case of attached convex hulls such a hyperplane doesn't exist.

Improve this question
$\endgroup$
11
  • $\begingroup$ Isn‘t this just the region of Tukey depth 2? $\endgroup$
    – Patrick Schnider
    Commented Dec 15, 2020 at 9:31
  • $\begingroup$ @PatrickSchnider only in the case where the dimension is 2 and the convex hull of the pointset is detached; for higher dimensions and detached convex hulls it is set of points of Tukey depth $n-1$. Thanks for pointing me to Tukey depth; I wasn't aware of that. $\endgroup$
    – Manfred Weis
    Commented Dec 15, 2020 at 11:52
  • $\begingroup$ Is there an easy example where the convex hull is not detached? $\endgroup$
    – Patrick Schnider
    Commented Dec 15, 2020 at 11:56
  • $\begingroup$ @PatrickSchnider I added an illustration; hope it clarifies matters. $\endgroup$
    – Manfred Weis
    Commented Dec 15, 2020 at 12:49
  • $\begingroup$ In the left picture, can‘t you cut off the topmost point using a line going through the rightmost point? Then the topmost point is not in your considered set, meaning the convex hull is detached? (I‘m probably missing something, sorry) $\endgroup$
    – Patrick Schnider
    Commented Dec 15, 2020 at 12:54

0

Reset to default

You must log in to answer this question.