New answers tagged computational-geometry
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 ...
0
As Discrete lizard pointed out in a comment, I misinterpreted the statement of "sharing a common point", which I read as "pairwise sharing a common point".
You can thus ignore the below answer. I will delete it later.
I'm not an expert in this area but I do actually believe that the problem you are talking about is surprisingly enough ...
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 ...
0
Your problem can be also stated as a counting version of the orthogonal range searching problem which is well studied in computational geometry. Let us see how.
Let $m_{i}$ denote the maximum $i^{th}$ coordinate value among all the points in $X$. Then, the query of finding $|D(z)|$ can be stated as follows:
Given an axis-parallel rectangle $R$ with the ...
2
Your problem is similar to finding Maxima of a point set in a $d$-dimensional space. In $2$-$D$ and $3$-$D$ there is a simple Divide and Conquer algorithm that has a $O(n \log n)$ running time. For higher dimension, there is $O(n (\log n)^{d-3}\log \log n)$ time algorithm as given in the Wikipedia page.
You can covert your problem to the Maxima problem, by ...
Top 50 recent answers are included
