最大密度矩形之找尋問題

Abstract

此篇論文中，我們探討在二維平面上尋找特定密度之矩形的方法。當二維平面退化成一維時，此問題已有最佳解O(nlogn)。若特定密度趨近無窮大，則有線性解O(n)。

We define the density finding problem on a rectangle(DFR for short) as follows. Given an m-by-n rectangle R, each unit block is attached with a value and a weight. A subrectangle S in R is an m′-by-n′ rectangle where 1 <= m′ <= m and 1 <= n′ <= n. The value(weight) of S is the sum of the value(weight) of each block in S. Let A and W be the value and weight of S respectively. The goal is to find a subrectangle S in R such that the density of S is closest to a specified real number δ, where the density of S is defined as the ratio of A and W, and L <= W <= U for two specified positive numbers L and U. When m = 1, Luo et al. [10] give a O(nlog n) time solution. Moreover, if δ → ∞, Chung et al. [5] and Bernholt et al. [3] both give O(n) time solutions in different ways. In this thesis, we will give a O(m^2nlog n) time solution for any δ and O(m^2n) time solution if δ → ∞ when m < n. Besides, we show that solving DFR takes Omega(mnlog n) when m < n.