hide
In this paper, we prove the space lower bound of Ω(N(log log N)^ε) space, for some constant ε > 0, for any cache-oblivious data structure capable of solving the following problems with optimal query time of O(log_B N + K / B) (or even query time of O((log_B N)^c (1 + K / B))):

• three-sided reporting queries in 2D
• dominance range reporting queries in 3D
• halfspace range reporting in 3D
• K-nearest neighbor queries in 2D

All these problems can be solved with O(log_B N + K / B) query with either linear or O(N log^*N) space. Thus, our lower bounds provide separation results for cache-oblivious and I/O models, proving on all these problems cache-oblivious model is always weaker than the I/O model.

An interesting open question is whether a lower bound of Ω(N log log N) is possible.

details...

hide
In this paper, we prove the following problems can be solved with O(N log N) space and O(log_B N + K / B) query I/Os in the cache-oblivious model:

• three-sided reporting queries in 2D
• dominance range reporting queries in 3D
• halfspace range reporting in 3D
• K-nearest neighbor queries in 2D

The main contribution of our paper is a technique to solve approximate range counting problem for all the above problems with optimal worst-case query and linear space in the cache-oblivious model. Except for orthogonal range counting in the plane, no such structures were known in the cache-oblivious model before. Furtherore, our approach is powerful enough to provide the first approximate halfspace range counting data structure with a worst-case query time of O(log (N / K)) in internal memory; previously, the same query bound was only known to hold in the expected case. We also provide a O(N log⁴ N) space cache-oblivious data structure with optimal query for 3D orthogonal range reporting.

An interesting open question is whether the space can be lowered to O(N log log N) for any of the above problems.

details...

hide
We give the first optimal solution to a standard problem in computational geometry: three-dimensional halfspace range reporting. We show that $n$ points in 3-d can be stored in a linear-space data structure so that all $k$ points inside a query halfspace can be reported in $O(\log n+k)$ time. The data structure can be built in $O(n\log n)$ expected time. The previous methods with optimal query time requires superlinear ($O(n\log\log n)$) space. We also mention consequences, for example, to higher dimensions and to external-memory data structures. As an aside, we partially answer another open question concerning the crossing number in Matoŭsek's shallow partition theorem in the 3-d case (a tool used in many known halfspace range reporting methods).

details...

hide
In this paper, we study the 3D dominance reporting problem in different models of computations and offer optimal results in the pointer machine and the external memory models and a near optimal result in the RAM model; all our results consume linear space. We can answer queries in O(\log n + k) time on a pointer machine, with O(\log_B n + k/B) I/Os in the external memory model and in O((\log\log n)^2 + \log\log U + k) time in the RAM model and in a UxUxU integer grid. These improve the results of various papers, such as Makris and Tsakalidis (IPL'98), Vengroff and Vitter (STOC'96) and Nekrich (SOCG'07).
With a \log^3 n fold increase in the space complexity these can be turned into orthogonal range reporting algorithms with matching query times, improving the previous orthogonal range searching results in the external memory and RAM models. Using our 3D results as base cases, we can provide improved orthogonal range reporting algorithms in \R^d, d \ge 4. We use randomization only in the preprocessing part and our query bounds are all worst case.

details...

hide
In this paper we study the problem of approximating the simplicial depth of a point in $\R^d$ with relative error of $\varepsilon$ for an arbitrary constant $\varepsilon > 0$. For $d=2$ we obtain the first algorithm which uses near linear space and can answer approximate simplicial depth queries in polylogarithmic expected time. This planar data structure can be used to approximate the simplicial depth of a given point in higher dimensions. The correctness of our results hold with high probability. Furthermore, we derive tight bounds relating the simplicial depth to Tukey depth.

details...

hide

We prove that if A^* is the largest subset of diameter r of n points in the Euclidean space, then for every \epsilon>0 there exists a polynomial time algorithm that outputs a set B of size at least |A^*| and of diameter at most r(\sqrt{2}+\epsilon). However, we show that unless P=NP for every \epsilon>0 it is not possible to guarantee the diameter r(\sqrt{4/3}-\epsilon) for B even if the algorithm is allowed to output a set of size ({95\over 94}-\epsilon)^{-1}|A^*|.

This problem can be viewed at an approximate version of a generalization of maximum clique and a few other related problems. Thus, our results imply that the best possible approximation factor lies between \sqrt{2}+\epsilon and \sqrt{4/3}-\epsilon. Our intuition is that the correct approximate factor is close to \sqrt{2}.

details...

hide
We improve the previous results by Aronov and Har-Peled (SODA'05) and Kaplan and Sharir (SODA'06) and present a randomized data structure of O(n) expected size which can answer 3D approximate halfspace range counting queries in O(\log{n\over k}) expected time, where k is the actual value of the count. This is the first optimal method for the problem in the standard decision tree model; moreover, unlike previous methods, the new method is Las Vegas instead of Monte Carlo. In addition, we describe new results for several related problems, including approximate Tukey depth queries in 3D, approximate regression depth queries in 2D, and approximate linear programming with violations in low dimensions.

details...

hide

We consider the problem of two-dimensional output-sensitive convex hull in the cache-oblivious model. Previously, optimal bounds were known only in the cache aware model and no output sensitive results were mentioned in the cache oblivious model. We use the following notation to describe our results: N (number of points), H (output size) B (block size), M (cache size), n=N/B, m=M/B, h=H/B.

From cache aware model, there exists a lower bound of n\log_m h and we almost match this lower bound with n\log_m h + n\log\log m cache misses. Whether this is the best possible result or there is still room for improvement remains an open question.

details...

hide
A problem born from a discussion group: how many vertex queries are needed in the worst case to find (or "learn") an unknown cut in a graph?

It turns out when there are small connected components at each side of the cut, then the problem has a trivial worst case but if we assume there are no small connected components after removing the cut, then the problem becomes interesting and non-trivial.

We solve the problem using a few similar assumptions and show that there exists an algorithm with the worst case query complexity of O(k)+2k\log{n\over k} in which k is the number of vertices adjacent to cut-edges. We also provide a matching lowerbound and also show that it is possible to remove our extra assumptions but achieve an approximate solution.

details...

hide

Given a set of points in space a unit disk-graph is obtained by connecting points within distance 1 of each other. In this paper we investigate two versions of the problem which are: (i) finding a largest subset of points with diameter at most one, and (ii) finding a subset of k points with minimum diameter. For the former problem we suggest several polynomial-time algorithms with constant approximation factors, the best of which has factor $\pi/\arccos(1/3)< 2.553$. For the latter problem we observe that there is a polynomial-time approximation scheme.

This paper is now almost obsolete. The following paper improves almost all our results.

An interesting open problem is whether finding the maximum clique in a unit disk-graph in 3D is NP-hard.

details...

hide
An old problem from undergrad days:

A defining set is a minimal set that uniquely determines the combinatorial concept assigned to it. This is also called the critical sets or sometimes even other names are used. For instance, a defining set for a perfect matching in a graph is a minimal set of edges that can be uniquely extended to that perfect matching. In this paper we show that for a certain grid like graphs the set containing size of all the defining sets for perfect matchings is a set of consecutive integers.

An interesting (and old) conjecture in this area is whether the size any defining set for a latin square is at least n^2/4, or alternatively, to prove or disprove that if one fixes less than n^2/4 elements of a latin square then this subset can be either extended to zero or more than one latin square. I'm not actively researching this area anymore so the status of this conjecture might have changed.

details...