請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38392
標題: Computing the Largest Empty Rectangle
作者: B.Chazelle
R.L.Drysdale
D.T.Lee
關鍵字: computational geometry
divide-and-conquer
free tree
location theory
optimization
摘要: Abstract. We consider the following problem: Given a rectangle containingN points, find the largest area subrectangle with sides parallel to those of the original rectangle which contains none of the given points. If the rectangle is a piece of fabric or sheet metal and the points are flaws, this problem is finding the largest-area rectangular piece which can be salvaged. A previously known result [13] takes O(N2) worst-case and O(N log N) expected time. This paper presents an O(N log N) time, O(N log N) space algorithm to solve this problem. It uses a divide-and-conquer approach similar to the ones used by Bentley [1] and introduces a new notion of Voronoi diagram along with a method for efficient computation of certain functions over paths of a tree.
URI: http://hdl.handle.net/11455/38392
顯示於類別:資訊科學與工程學系所

文件中的檔案:
沒有與此文件相關的檔案。


在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。