Subhas C. Nandy
Inplace Algorithm for Priority Search Tree and its use in Computing Largest Empty Axis-Parallel Rectangle.
Mon, 04/18/2011 - 15:01 — SomNambulAuthors: Subhas C. Nandy, Minati De
Subjects: Computational Geometry
AbstractThere 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.Approximation Algorithm for Line Segment Coverage for Wireless Sensor Network.
Wed, 06/16/2010 - 15:01 — SomNambulAuthors: Arijit Bishnu, Dinesh Dash, Arobinda Gupta, Subhas C. Nandy
Subjects: Computational Geometry
AbstractThe coverage problem in wireless sensor networks deals with the problem of
covering a region or parts of it with sensors. In this paper, we address the
problem of covering a set of line segments in sensor networks. A line segment `
is said to be covered if it intersects the sensing regions of at least one
sensor distributed in that region. We show that the problem of ?nding the
minimum number of sensors needed to cover each member in a given set of line
segments in a rectangular area is NP-hard.
User login
