Finding Maximum Density Axes Parallel Regions for Weighted Point Sets.
Ananda Swarup Das, Prosenjit Gupta, Kannan Srinathan, Kishore Kothapalli · Canadian Conference on Computational Geometry · 2011
In this work we study the problem of nding axes- parallel regions of maximum density for weighted point sets in IR 2 and IR 3 . The 2-d variant is motivated by applications in thermal analysis of VLSI chips. n log logn ) storage. We nally discuss how to nd the highest density axes parallel 3-dimensional box provided the coordinates of the n weighted points are integers in (0;U) (0;U) (0;U). Special note: We assume that all the coordinates of the points are distinct. This particular assumption of distinctness is important for the correctness of the so- lution as because, if there are two points whose x co- ordinates (or y coordinates) are the same, the area of the axes parallel rectangle induced by them is zero and hence the corresponding density will be1.