Let $\mathbb{R}^d$ be $d$-dimensional Euclidean space
Let $\Delta=\{x\in\mathbb{R}^d_+:\sum_{i=1}^dx^i\leq1\}$ ($x^i$ is the i-th coordinate of $x$)
(Equivalently, $\Delta$ is the convex hull of $\{(0,\cdots,0),(1,0,\cdots,0),(0,1,0,\cdots,0),\cdots,(0,\cdots,0,1)\}$)
Let $A=\{x_1,\cdots,x_k\}\subset\Delta$
Let $y\in\Delta$

Consider the set $C\equiv\{z\in\mathbb{R}^d:z=y+\sum_{i=1}^k\lambda_i(x_i-y)\mbox{ for some }(\lambda_i)_{i=1}^k\mbox{ such that }\lambda_i\geq0\ \forall i\}$
That is, $C$ is ($y$ + the hull of nonnegative linear combinations of $A-y$)
Note that $C$ is a closed convex cone with apex at $y$

I have two questions related to computational geometry.
Q1: How to compute $C$? I think $C$ can be expressed as the intersection of finitely many half-spaces (because $C$ is a polyhedron, right?). Is there an algorithm to find out those half-spaces?
Q2: How to compute the set of all extreme points of $\Delta\cap C$? I think there are only finitely many extreme points, right? Is there an algorithm?

I have no background in computational geometry. I'd love to see any reference, book or paper, so I can cite. Thanks for any help!


Not a direct answer, but a few references that might lead you to the appropriate literature.

The intersection of $k$ polytopes discusses "the intersection of finitely many half-spaces":

Fukuda, Komei, Thomas M. Liebling, and Christine Lütolf. "Extended convex hull." Comput. Geom. 20, no. 1-2 (2001): 13-23. (Elsevier link.)
Abstract. In this paper we address the problem of computing a minimal representation of the convex hull of the union of $kH$-polytopes in $\mathbb{R}^d$. [...]

          (Image from Fukuda et al..)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.