登入選單
返回Google圖書搜尋
其他書名
Topology, Combinatorics, and Algorithms
出版Department of Computer Science, University of Illinois at Urbana-Champaign, 1988
URLhttp://books.google.com.hk/books?id=OprS7xIAqf4C&hl=&source=gbs_api
註釋Arrangements of curves in the plane are fundamental to many problems in computational and combinatorial geometry (e.g. motion planning, algebraic cell decomposition, etc.). In this paper we study various topological and combinatorial properties of such arrangements under some mild assumptions on the shape of the curves, and develop basic tools for the construction, manipulation, and analysis of these arrangements. Our main results include a generalization of the zone theorem of [EOS], [CGL] to arrangements of curves (in which we show that the combinatorial complexity of the zone of a curve is nearly linear in the number of curves), and an application of that theorem to obtain a nearly quadratic incremental algorithm for the construction of such arrangements.