Placement of K Disjoint Isothetic Unit Squares to Maximize Points Containment

Main Article Content

Priya Ranjan Sinha Mahapatra

Abstract

Given a set P of n points in the two dimensional plane, we propose ( ) 2 5 O k n time and ( ) 4 O kn space algorithm to locate
k isothetic unit squares which are pairwise disjoint and they together contain maximum number of points from P . Moreover, an
( log ) 2 O n n time and O(n) space algorithm is demonstrated for k = 2.

 

 

Keywords: Isothetic; Space Partition Tree; Sliceable; Np-hard.

Downloads

Download data is not yet available.

Article Details

Section
Articles