Variations of Enclosing Problem Using Axis Parallel Square(s): A General Approach

HTML  Download Download as PDF (Size: 373KB)  PP. 197-205  
DOI: 10.4236/ajcm.2014.43016    5,560 Downloads   7,268 Views  Citations

ABSTRACT

Let P be a set of n points 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 n squares 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 , .

Share and Cite:

Mahapatra, P. (2014) Variations of Enclosing Problem Using Axis Parallel Square(s): A General Approach. American Journal of Computational Mathematics, 4, 197-205. doi: 10.4236/ajcm.2014.43016.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.