Name
Title | ||
|---|---|---|
Inplace Algorithm for Priority Search Tree and its use in Computing Largest Empty Axis-Parallel Rectangle |
Abstract | ||
|---|---|---|
There is a high demand of space-efficient algorithms in built-in or embedded softwares. In this paper, we consider the problem of designing space-efficient algorithms for computing the maximum area empty rectangle (MER) among a set of points inside a rectangular region $\cal R$ in 2D. We first propose an inplace algorithm for computing the priority search tree with a set of $n$ points in $\cal R$ using $O(\log n)$ extra bit space in $O(n\log n)$ time. It supports all the standard queries on priority search tree in $O(\log^2n)$ time. We also show an application of this algorithm in computing the largest empty axis-parallel rectangle. Our proposed algorithm needs $O(n\log^2n +m)$ time and $O(\log n)$ work-space apart from the array used for storing $n$ input points. Here $m$ is the number of maximal empty rectangles present in $\cal R$. Finally, we consider the problem of locating the maximum area empty rectangle of arbitrary orientation among a set of $n$ points, and propose an $O(n^3\log n)$ time in-place algorithm for that problem. |
Year | Venue | Keywords |
|---|---|---|
2011 | Clinical Orthopaedics and Related Research | computational geometry,embedded software |
Field | DocType | Volume |
Binary logarithm,Discrete mathematics,Combinatorics,Largest empty rectangle,Rectangle,Algorithm,Mathematics,Search tree | Journal | abs/1104.3 |
Citations | PageRank | References |
2 | 0.38 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Minati De | 1 | 45 | 10.11 |
| Subhas C. Nandy | 2 | 285 | 49.55 |