On Levels in Arrangements of Curves

   Abstract. Analyzing the worst-case complexity of the k -level in a planar arrangement of n curves is a fundamental problem in combinatorial geometry. We give the first subquadratic upper bound (roughly O( nk^ 1-1/(9· 2 ^s-3 ) ) ) for curves that are graphs of polynomial functions of an arbitrary fixed degree s . Previously, nontrivial results were known only for the case s=1 and s=2 . We also improve the earlier bound for pseudo-parabolas (curves that pairwise intersect at most twice) to O( nk ^7/9 log ^2/3 k) . The proofs are simple and rely on a theorem of Tamaki and Tokuyama on cutting pseudo-parabolas into pseudo-segments, as well as a new observation for cutting pseudo-segments into pieces that can be extended to pseudo-lines. We mention applications to parametric and kinetic minimum spanning trees.     

On Levels in Arrangements of Curves

Abstract. Analyzing the worst-case complexity of the k -level in a planar arrangement of n curves is a fundamental problem in combinatorial geometry. We give the first subquadratic upper bound (roughly O( nk^ 1-1/(9· 2 ^s-3 ) ) ) for curves that are graphs of polynomial functions of an arbitrary fixed degree s . Previously, nontrivial results were known only for the case s=1 and s=2 . We also improve the earlier bound for pseudo-parabolas (curves that pairwise intersect at most twice) to O( nk ^7/9 log ^2/3 k) . The proofs are simple and rely on a theorem of Tamaki and Tokuyama on cutting pseudo-parabolas into pseudo-segments, as well as a new observation for cutting pseudo-segments into pieces that can be extended to pseudo-lines. We mention applications to parametric and kinetic minimum spanning trees.     

On Levels in Arrangements of Lines, Segments, Planes, and Triangles%

We consider the problem of bounding the complexity of the k th level in an arrangement of n curves or surfaces, a problem dual to, and an extension of, the well-known k-set problem. Among other results, we prove a new bound, O(nk ^5/3 ) , on the complexity of the k th level in an arrangement of n planes in R ³ , or on the number of k -sets in a set of n points in three dimensions, and we show that the complexity of the k th level in an arrangement of n line segments in the plane is , and that the complexity of the k th level in an arrangement of n triangles in 3-space is O(n ² k ^5/6 α(n/k)) . <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p315.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received February 7, 1997, and in revised form May 15, 1997, and August 30, 1997.     

On Levels in Arrangements of Surfaces in Three Dimensions

A favorite open problem in combinatorial geometry is to determine the worst-case complexity of a level in an arrangement. Up to now, nontrivial upper bounds in three dimensions are known only for the linear cases of planes and triangles. We propose the first technique that can deal with more general surfaces in three dimensions. For example, in an arrangement of n ??pseudo-planes?? or ??pseudo-spherical patches?? (where the main criterion is that each triple of surfaces has at most two common intersections), we prove that there are at most O(n ^2.997) vertices at any given level.     

关于Alzer不等式的一个简单证明

利用数学归纳法和函数的单调性，本给出了Alzer不等式的一个简单证明．     

On the Number of Simple Arrangements of Five Double Pseudolines

We describe an incremental algorithm to enumerate the isomorphism classes of double pseudoline arrangements. The correction of our algorithm is based on the connectedness under mutations of the spaces of one-extensions of double pseudoline arrangements, proved in this paper. Counting results derived from an implementation of our algorithm are also reported.     

关于Hilbert不等式及其应用

设a,b为任意复数,证明了如下的不等式:其中A=A(a,b)为一实数。此不等式显然为Hilber不等式有意义的改进。 若b=a,则上述不等式中可取。应用此结果,立即得到Fejer-Riesz型不等式。     

Opial－Olech型不等式的改进及其应用

本文给出：设ｆ（ｘ）在［０，ｈ］上绝对连续。ｆ（０）＝ｆ（ｈ）＝０，ｐ＞０，ｑ＞１和ｓ＝Ｐ／（ｐ＋ｑ－１），则有 其中θ（ｐ）＝1/2,p+q>0,θ（ｐ）＝P/2.当１＜ｐ＋ｑ＜２.若代（Ａ）右边为零。即为Ｏｐｉａｌ－Ｏｌｃｃｈ不等式。实际上本文所得结果还要广泛。     

关于hilbert－ingham不等式和它的应用

本文给出（ｉ）ｈｉｌｂｅｒｔ不等式和ｈｉｌｂｅｒｔ－ｉｎｇｈａｍ不等式一些有意义的共同改进；（ｉｉ）一些ｆｅｊｅｒ－ｒｉｅｓｚ型不等式的改进和（ｉｉｉ）ｈａｒｄｙ不等式的改进．     

Fuk-Nagaev型不等式的推广及应用

本文首先对具有ｐ（１〈ｐ≤２）阶矩的独立Ｂ值随机变量列（Ｘｎ）研究了Ｆｕｋ－Ｎａｇａｅｖ型不等式,进而得出重对数律的一些结果。     

A FUNDAMENTAL INEQUALITY AND ITS APPLICATION

Let f(z) be meromorphie in |z|k+4+[2/k].In this note,a fundamental inequality is established such that thecharacreristic function T(r,f)can be limibd by N(r,1/f)and _(τ-1)(r,1/(f~(k)-1).As anapplication,the following criterion for normality is also proved:Let be a family ofmeromorphic functions in a region D.If for every f(z)∈ ,f(z)≠0 and all the zeros off~(k)(z)-1 are of multiplicity >k+4+[2/k]in D,then is normal there.     

一类差分不等式及其应用

建立一类二变量的和差分不等式,该不等式包含了一个一重和与两个二重和,二重和号内包含两个不同的没有假设单调性的未知函数的复合函数.使用单调化技术,利用了强单调的性质,给出了差分不等式中未知函数的估计.结果能使我们对相关文献中考虑的差分不等式中未知函数进行估计.进一步,用结果给出了一类差分方程解的估计.     

关于Hardy-Hilbert积分不等式及其等价形式

In this paper, by introducing three parameters a, b and λ, we give some new generalizations of Hardy-Hilbert's integral inequality. As applications, we con-sider its equivalent form and some particular results.     

On a Refinement of Hardy-Hilbert's Inequality and Its Applications

§1. Introduction If p＞1, 1p+1q=1, an≥0, bn≥0, and 0＜∑∞n=1-λapn＜∞, 0＜∑∞n=1-λbqn＜∞ (λ=0,1), then∑∞m=1-λ∑∞n=1-λambnm+n+λ＜πsin(π/p)∑∞n=1-λapn1/p∑∞n=1-λbqn1/q,(1.1)where the constant π／sinπp is best possible for λ=0, or 1. For λ=0,1, (1.1) is named of HardyHilberts inequality, which is important in analysis and applications (see ［1］, Chapt. 9). On (1.1) for λ=0, by estimating a weight coefficient, Xu［2］ gave a refinement as∑∞m=1∑∞n=1ambnm+n＜∑∞n=…     

A Simple Proof of the Jensen-Type Inequality of Fink and Jodeit

We discuss the extension of Jensen’s inequality to the framework of quasiconvex functions. Moreover, it is proved that our results work for a class of signed measures larger than the class of probability measures.     

Arrangements on Parametric Surfaces II: Concretizations and Applications

We describe the algorithms and implementation details involved in the concretizations of a generic framework that enables exact construction, maintenance, and manipulation of arrangements embedded on certain two-dimensional orientable parametric surfaces in three-dimensional space. The fundamentals of the framework are described in a companion paper. Our work covers arrangements embedded on elliptic quadrics and cyclides induced by intersections with other algebraic surfaces, and a specialized case of arrangements induced by arcs of great circles embedded on the sphere. We also demonstrate how such arrangements can be used to accomplish various geometric tasks efficiently, such as computing the Minkowski sums of polytopes, the envelope of surfaces, and Voronoi diagrams embedded on parametric surfaces. We do not assume general position. Namely, we handle degenerate input, and produce exact results in all cases. Our implementation is realized using Cgal and, in particular, the package that provides the underlying framework. We have conducted experiments on various data sets, and documented the practical efficiency of our approach.