New answers tagged

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