登入選單
返回Google圖書搜尋
出版University of Illinois at Urbana-Champaign, Department of Computer Science, 1991
URLhttp://books.google.com.hk/books?id=Kf1Y4-Q6YocC&hl=&source=gbs_api
註釋Abstract: "The zone theorem for an arrangement of n hyperplanes in d-dimensional real space says that the total number of faces bounding the cells intersected by another hyperplane is O(n[superscript d-1]). This result is the basis of a time-optimal incremental algorithm that constructs a hyperplane arrangement and has a host of other algorithmic and combinatorial applications. Unfortunately, the original proof of the zone theorem, for d[greater than or equal to]3, turned out to contain a serious and irreparable error. This paper presents a new proof of the theorem. Our proof is based on an inductive argument, which also applies in the case of pseudo-hyperplane arrangements. We also briefly discuss the fallacies of the old proof along with some ways of partially saving that approach."