On Finding the Maximum and Minimum Density Axes-parallel Regions in IR^d

Article type: Research Article

Authors: Basu, Nilanjana G.^{a; *} | Majumder, Subhashis^a | Hon, Wing Kai^b

Affiliations: [a] Computer Science & Engineering Department, Heritage Institute of Technology, Kolkata, India. nilanjanag.basu@heritageit.edu, subhashis.majumder@heritageit.edu | [b] Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 300, wkhon@cs.nthu.edu.tw

Correspondence: [*] Address for correspondence: Computer Science & Engineering Department, Heritage Institute of Technology, Chowbaga Road Kolkata - 700107, India.

Abstract: Finding the density of a set of n points, especially where points are in IR2 or IR3, has direct applications in thermal analysis of VLSI chips. In this paper, we consider identifying the maximum-density axes-parallel region for a set of weighted points in IRd for d ≥ 2, and show that it can be done in O(dn2) time. We also consider finding the minimum-density axes-parallel region, and show that for IR2 the problem can be solved in O(n2) time.

Keywords: MER, density, Axes-parallel

DOI: 10.3233/FI-2017-1509

Journal: Fundamenta Informaticae, vol. 152, no. 1, pp. 1-12, 2017