On Finding the Maximum and Minimum Density Axes-parallel Regions in Rd

Finding the density of a set of n points, especially where points are in R2 or R3, 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 R2 the problem can be solved in O(n2) time.

---

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).