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

• 作者: Priya Ranjan Sinha Mahapatra
• 来源期刊: 美国计算数学期刊(英文)
• 学科: 数学
• 关键词: Axis-Parallel Unit SQUARE SWEEP Line Algorithm Maximium Enclosing PROBLEM K-Enclosing PROBLEM
• 年，卷（期）: 2014,（3）
• 页码范围: 197-205
• 页数: 9页
• 分类号: O1

摘要

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 , .