首页 | 本学科首页   官方微博 | 高级检索  
     检索      


The complexity and construction of many faces in arrangements of lines and of segments
Authors:Herbert Edelsbrunner  Leonidas J Guibas  Micha Sharir
Institution:(1) Department of Computer Science, University of Illinois at Urbana-Champaign, 61801 Urbana, Ill, USA;(2) DEC Systems Research Center, 130 Lytton Avenue Palo Alto, 94301, Ca, USA;(3) Department of Computer Science, Stanford University, 94305, Ca, USA;(4) Courant Institute of Mathematical Sciences, New York University, 10012 New York, NY, USA;(5) School of Mathematical Science, Tel Aviv University, 69978 Tel Aviv, Israel
Abstract:We show that the total number of edges ofm faces of an arrangement ofn lines in the plane isO(m 2/3–delta n 2/3+2delta +n) for anydelta>0. The proof takes an algorithmic approach, that is, we describe an algorithm for the calculation of thesem faces and derive the upper bound from the analysis of the algorithm. The algorithm uses randomization and its expected time complexity isO(m 2/3–delta n 2/3+2delta logn+n logn logm). If instead of lines we have an arrangement ofn line segments, then the maximum number of edges ofm faces isO(m 2/3–delta n 2/3+2delta +nagr (n) logm) for anydelta>0, whereagr(n) is the functional inverse of Ackermann's function. We give a (randomized) algorithm that produces these faces and takes expected timeO(m 2/3–delta n 2/3+2delta log+nagr(n) log2 n logm).The first author is pleased to acknowledge partial support by the Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and the National Science Foundation under Grant CCR-8714565. Work on this paper by the third author has been supported by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation Grant DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD-the Israeli National Council for Research and Development. A preliminary version of this paper has appeared in theProceedings of the 4th ACM Symposium on Computational Geometry, 1988, pp. 44–55.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号