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

• Autorzy: Basu N. G. , Majumder S. , Hon W. K.

Identyfikatory

DOI

10.3233/FI-2017-1509

• Języki publikacji: EN

Abstrakty

EN

Finding the density of a set of n points, especially where points are in R² or R³, 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 IR^d for d ≥ 2, and show that it can be done in O(dn²) time. We also consider finding the minimum-density axes-parallel region, and show that for R² the problem can be solved in O(n²) time.

Słowa kluczowe

EN

Axes-parallel; density; MER

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 152, nr 1
• Strony: 1--12
• Opis fizyczny: Bibliogr. 6 poz., wykr.

Twórcy

autor

Basu N. G.

• Computer Science & Engineering, Department Heritage Institute of Technology, Kolkata, India

autor

Majumder S.

• Computer Science & Engineering, Department Heritage Institute of Technology, Kolkata, India

autor

Hon W. K.

• Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 300

Bibliografia

• [1] Majumder S, Sur-Kolay S, Nandy SC, Bhattacharya BB, Chakraborty B. Hot Spots and Zones in a Chip: A Geometrician’s View. Proceedings of the IEEE 18-th International Conference on VLSI Design, January 03-07 2005, pp. 691–696. doi:10.1109/ICVD.2005.106.
• [2] Tsai CH, Kang SM. Cell-Level Placement for Improving Substrate Thermal Distribution. IEEE TCAD, 2000;19(2):253–266. doi:10.1109/43.828554.
• [3] Majumder S, Bhattacharya BB. On the Density and Discrepancy of a 2D Point Set with Applications to Thermal Analysis of VLSI chips. Information Processing Letter, 2008;107(5):177–182. doi:10.1016/j.ipl.2008.02.011.
• [4] Das AS, Gupta P, Srinathan K, Kothapalli K. Finding the Maximum Density Axes Parallel Regions for Weighted Point Sets. Proceedings of the 23rd Annual Canadian Conference on Computational Geometry (CCCG), Toronto, Ontario, Canada, August 10-12, 2011. doi:10.1.1.381.1806.
• [5] Aggarwal A, Klawe M, Moran S, Shor P, Wilber R. Geometric Applications of a Matrix Searching Algorithm. Algorithmica, 1987;2:195–208. doi:10.1007/BF01840359.
• [6] Aggarwal A, Suri S. Fast Algorithms for Computing the Largest Empty Rectangle. Proceeding of the third Annual Symposium on Computational Geometry (SCG ’87)Waterloo, Ontario, Canada 1987, pp. 278–290. doi:10.1145/41958.41988.

Uwagi

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