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
Related Tags
computational-geometry × 683algorithms × 373
data-structures × 56
graphs × 51
optimization × 48
polygons × 33
complexity-theory × 31
time-complexity × 25
graphics × 25
reference-request × 22
computer-vision × 20
discrete-mathematics × 19
convex-hull × 19
image-processing × 15
euclidean-distance × 14
linear-algebra × 13
search-algorithms × 12
approximation × 12
linear-programming × 12
voronoi-diagrams × 12
algorithm-analysis × 9
np-complete × 9
doubly-connected-edge-list × 9
divide-and-conquer × 8
nearest-neighbour × 8