3

I suspect that if the points in your set are expressed as $Ax \le b$ and you're considering the Euclidean distance, then you can solve the following quadratic program with the ellipsoid method: $$ \max \sum_i (x^2_i+y^2_i-2x_i y_i) \\ Ax \le b \\ Ay \le b. $$ Where we used the fact that optimizing $|x-y|$ is the same as optimizing $ \frac{1}{2} |x-y|^2 = \...


1

Here is one approach you could consider. If the number of non-missing coordinates is tightly concentrated around 10, it might help you partly avoid the curse of dimensionality. I don't know whether it will be useful in practice. Choose a random hash function $h:\{1,\dots,d\} \to \{1,\dots,10\}$. If $x \in \mathbb{R}^d$ is a data point, let $f(x)$ be its ...


1

Algorithm. We maintain a set $S$, which is initially a set of vertices of $X$. Let $CH(S)$ be the convex hull of $S$. We want to find $S$ such that $CH(S) \subset Z$ is a maximal polygon. We first define operation $extend(s,t)$ which Finds a point $x$ on the ray starting from $s$ and going through $t$ such that $CH(S \cup \{x\}) \subset Z$ and $x$ is the ...


1

I had the same problem when I was trying to simulate the Projection-Slice-Theorem. A quick solution is to use generalized bivariate interpolations, e.g. from random sample points to rectangular grid (not specific to your problem , but will work, example in python here https://docs.scipy.org/doc/scipy/reference/generated/scipy.interpolate.griddata.html#scipy....


Only top voted, non community-wiki answers of a minimum length are eligible