Name
Abstract | ||
|---|---|---|
Prune-and-search is an important paradigm for solving many important geometric problems. We show that the general prune-and-search technique can be implemented where the objects are given in read-only memory. As examples we consider convex-hull in 2D, and linear programming in 2D and 3D. For the convex-hull problem, designing sub-quadratic algorithm in a read-only setup with sub-linear space is an open problem for a long time. We first propose a simple algorithm for this problem that runs in $O(n^{3/2+\epsilon)}$ time and $O(n^(1/2))$ space. Next, we consider a restricted version of the problem where the points in $P$ are given in sorted order with respect to their $x$-coordinates in a read-only array. For the linear programming problems, the constraints are given in the read-only array. The last three algorithms use {\it prune-and-search}, and their time and extra work-space complexities are $O(n^{1 + \epsilon})$ and $O(\log n)$ respectively, where $\epsilon$ is a small constant satisfying $\sqrt{\frac{\log\log n}{\log n}} < \epsilon < 1$. |
Year | Venue | Field |
|---|---|---|
2012 | CoRR | Binary logarithm,Discrete mathematics,Combinatorics,Open problem,Convex hull,Geometric problems,Linear programming,SIMPLE algorithm,Mathematics |
DocType | Volume | Citations |
Journal | abs/1212.5353 | 4 |
PageRank | References | Authors |
0.43 | 4 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Minati De | 1 | 45 | 10.11 |
| Subhas C. Nandy | 2 | 285 | 49.55 |
| Sasanka Roy | 3 | 31 | 13.37 |