TITLE:
Variations of Enclosing Problem Using Axis Parallel Square(s): A General Approach
AUTHORS:
Priya Ranjan Sinha Mahapatra
KEYWORDS:
Axis-Parallel Unit Square, Sweep Line Algorithm, Maximium Enclosing Problem, K-Enclosing Problem
JOURNAL NAME:
American Journal of Computational Mathematics,
Vol.4 No.3,
May
16,
2014
ABSTRACT:
Let P be a set of npoints in two dimensional plane. For each
point , we locate an axis- parallel unit square having one particular side passing
through p and enclosing the maximum number of points
from P. Considering all
points , such nsquares can be reported in O(nlogn)time. We show that this result can be used to
(i) locate m>(2)axis-parallel unit squares which are pairwise
disjoint and they together enclose the maximum number of points from P (if exists) and (ii) find the smallest
axis-parallel square enclosing at least k points of P , .