最大密度矩形之找尋問題

Density Finding on a Rectangle

羅偉力

指導教授 ： 蔡錫鈞

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.00101

摘要

此篇論文中，我們探討在二維平面上尋找特定密度之矩形的方法。當二維平面退化成一維時，此問題已有最佳解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.

並列關鍵字

Density Finding ； Algorithm ； Time Complexity

參考文獻

[1] Alok Aggarwal and Maria Klawe. Applications of generalized matrix searching to geometric algorithms. Discrete Applied Mathematics, 27:3–23, 1990.

on Theory of computing, pages 80–86, 1983.

[3] Thorsten Bernholt, Friedrich Eisenbrand, and Thomas Hofmeister. A geometric framework for solving subsequence problems in computational biology efficiently. In

[4] B. Chazelle, R.L.Drysdale, and D.T.Lee. Computing the largest empty rectangle. SIAM Journal of Computing, 15(1):300–315, 1986.

[5] Kai-Min Chung and Huseh-I Lu. An optimal algorithm for the maximum-density segment problem. SIAM J. COMPUT., 34(2):373–387, 2004.