Computer Science – Computational Geometry
Scientific paper
2011-04-15
Computer Science
Computational Geometry
14 pages, 5 figures
Scientific paper
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.
De Minati
Nandy Subhas C.
No associations
LandOfFree
Inplace Algorithm for Priority Search Tree and its use in Computing Largest Empty Axis-Parallel Rectangle does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Inplace Algorithm for Priority Search Tree and its use in Computing Largest Empty Axis-Parallel Rectangle, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inplace Algorithm for Priority Search Tree and its use in Computing Largest Empty Axis-Parallel Rectangle will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-9028