How hard is half-space range searching?

We investigate the complexity ofhalf-space range searching: givenn points ind-space, build a data structure that allows us to determine efficiently how many points lie in a query half-space. We establish a tradeoff between the storagem and the worst-case query timet in the Fredman/Yao arithmetic model of computation. We show thatt must be at least on the order of $$\frac{{(n/\log n)^{1 - (d - 1)/d(d + 1)} }}{{m^{1/d} }}$$ Although the bound is unlikely to be optimal, it falls reasonably close to the recent upper bound ofO(n/m ^1/d ) established by Matou?ek. We also show that it is possible to devise a sequence ofn inserts and half-space range queries that require a total time ofn ^2-O(1/d) . Our results imply the first nontrivial lower bounds for spherical range searching in any fixed dimension. For example, they show that, with linear storage, circular range queries in the plane require Ω(n ^1/3) time (modulo a logarithmic factor).     

Estimation of an algebraic polynomial in a plane in terms of its real part on the unit circle

We consider the class P _n ^* of algebraic polynomials of a complex variable with complex coefficients of degree at most n with real constant terms. In this class we estimate the uniform norm of a polynomial P _n ∈ P _n ^* on the circle Γ_r = z ∈ ?: ¦z¦ = r of radius r = 1 in terms of the norm of its real part on the unit circle Γ₁ More precisely, we study the best constant μ(r, n) in the inequality ||P_n||C(Γ_r) ≤ μ(r,n)||Re P_n||C(Γ₁). We prove that μ(r,n) = rⁿ for rⁿ⁺² ? r ⁿ ? 3r² ? 4r + 1 ≥ 0. In order to justify this result, we obtain the corresponding quadrature formula. We give an example which shows that the strict inequality μ(r, n) = r ⁿ is valid for r sufficiently close to 1.     

Probability estimates for the distribution of Kolmogorov distance in the worst direction

ConsiderD _n the maximum Kolmogorov distance betweenP _n andP among all possible one-dimensional projections, whereP _n is an empirical measure based ond-dimensional i.i.d vectors with spherically symmetric probability measureP. We show in this paper that $$c_1 \lambda ^2 \exp ( - 2\lambda ^2 ) \leqslant P(\sqrt n D_n > \lambda )$$ for large λ,d≥2 and an appropriate constantc ₁. From this, when dimensiond is fixed, we give a negative answer to Huber's conjecture,P(D _n >ε)≤N exp(?2n? ²), whereN is a constant depending only on dimensiond.     

Derivations with nilpotent values

IfR is a semiprme ring andd a derivation ofR such thatd(x) ⁿ=0 for allx∈R, wheren≥1 is a fixed integer, thend=0.     

Approximation of convex bodies by polytopes with uniformly bounded valences

Given any convex bodyK in Euclideann-spaceR ⁿ and any number ?>0, does there always exist a polytopeP(K, ?)?R ⁿ such that the number of vertices of a facet ofP and the number of facets meeting in a common vertex are bounded by a constant depending on the dimensiond only and such that the Hausdorff-distance ? (K, P) ofK andP is less than ?? This question of Ewald posed at the Durham symposium in 1975 is answered in the affirmative.     

Monadic Algebras with finite degree

A monadic algebraA has finite degreen ifA/M has at most 2 ⁿ elements for every maximal idealM ofA and this bound is obtained for someM. Every countable monadic algebra with a finite degree is isomorphic to an algebra Γ(X, S) whereX is a Boolean space andS is a subsheaf of a constant sheaf with a finite simple stalk. This representation is used to prove that every proper equational class of monadic algebras has a decidable first-order theory.     

A support property for infinite-dimensional interacting diffusion processes

The Dirichlet form associated with the intrinsic gradient on Poisson space is known to be quasi-regular on the complete metric space Γ = {ℤ₊-valued Radon measures on ℝ^d}. We show that under mild conditions, the set Γ\Γ is ɛ-exceptional, where Γ is the space of locally finite configurations in ℝ^d, that is, measures γ ε Γ satisfying sup_xε, γ({x}) ≤ 1. Thus, the associated diffusion lives on the smaller space Γ. This result also holds for Gibbs measures with superstable interactions.     

On the dimension of ordered sets with the 2-cutset property

An ordered setP is said to have 2-cutset property if, for every elementx ofP, there is a setS of elements ofP which are noncomparable tox, with |S|?2, such that every maximal chain inP meets {x}∪S. We consider the following question: Does there exist ordered sets with the 2-cutset property which have arbitrarily large dimension? We answer the question in the negative by establishing the following two results.Theorem: There are positive integersc andd such that every ordered setP with the 2-cutset property can be represented asP=X∪Y, whereX is an ordinal sum of intervals ofP having dimension ?d, andY is a subset ofP having width ?c. Corollary: There is a positive integern such that every ordered set with the 2-cutset property has dimension ?n.     

Inversion formulas for complex radon transform on projective varieties and boundary value problems for systems of linear PDEs

Let G ? ?P ⁿ be a linearly convex compact set with smooth boundary, D = ?P ⁿ \ G, and let D* ? (?P ⁿ )* be the dual domain. Then for an algebraic, not necessarily reduced, complete intersection subvariety V of dimension d we construct an explicit inversion formula for the complex Radon transform R _V : H ^d,d?1(V ∩ D) → H ^1,0(D*) and explicit formulas for solutions of an appropriate boundary value problem for the corresponding system of differential equations with constant coefficients on D*.     

Traces of monotone Sobolev functions

In this paper we prove that ifu: ${\mathbb{B}}^n \to {\mathbb{R}}$ , where ${\mathbb{B}}^n $ is the unit ball in ? ⁿ , is a monotone function in the Sobolev space W^1·p ( ${\mathbb{B}}^n $ ), andn ? 1 <p ≤n, thenu has nontangential limits at all the points of $\partial {\mathbb{B}}^n $ except possibly on a set ofp-capacity zero. The key ingredient in the proof is an extension of a classical theorem of Lindelöf to monotone functions in W^1·p ( ${\mathbb{B}}^n $ ),n ? 1 <p ≤n.     

A constructive description of Hölder classes on closed Jordan curves

Let Γ be a closed, Jordan, rectifiable curve, whose are length is commensurable with its subtending chord, leta ε int Γ, and let R_n(a) be the set of rational functions of degree ≤n, having a pole perhaps only at the pointa. Let Λ^α(Γ), 0 < α < 1, be the Hölder class on Γ. One constructs a system of weights γ_n(z) > 0 on Γ such that f∈Λ^α(Γ) if and only if for any nonnegative integer n there exists a function R_n, R_n ε R_n(a) such that ¦f(z) ? R_n(z)¦ ≤ c_f·γ_n(z), z ε Γ. It is proved that the weights γ_n cannot be expressed simply in terms of ρ ₁ ⁺ /n^(z) and ρ ₁ ^- /n^(z), the distances to the level lines of the moduli of the conformal mappings of ext Γ and int Γ on \(\mathbb{C}\backslash \mathbb{D}\) .     

Intersection properties of boxes in R d

A family of sets is calledn-pierceable if there exists a set ofn points such that each member of the family contains at least one of the points. Helly’s theorem on intersections of convex sets concerns 1-pierceable families. Here the following Helly-type problem is investigated: Ifd andn are positive integers, what is the leasth =h(d, n) such that a family of boxes (with parallel edges) ind-space isn-pierceable if each of itsh-membered subfamilies isn-pierceable? The somewhat unexpected solution is: (i)h(d, 2) equals3d for oddd and 3d?1 for evend; (ii)h(2, 3)=16; and (iii)h(d, n) is infinite for all (d, n) withd≧2 andn≧3 except for (d, n)=(2, 3).     

Lemniscates and inequalities for the logarithmic capacities of continua

It is shown that if P(z) = z ⁿ + ? is a polynomial with connected lemniscate E(P) = {z: ¦P(z)¦ ≤ 1} and m critical points, then, for any n? m+1 points on the lemniscate E(P), there exists a continuum γ ? E(P) of logarithmic capacity cap γ ≤ 2^?1/n which contains these points and all zeros and critical points of the polynomial. As corollaries, estimates for continua of minimum capacity containing given points are obtained.     

Applications of random sampling in computational geometry,II

We use random sampling for several new geometric algorithms. The algorithms are Las Vegas, and their expected bounds are with respect to the random behavior of the algorithms. These algorithms follow from new general results giving sharp bounds for the use of random subsets in geometric algorithms. These bounds show that random subsets can be used optimally for divide-and-conquer, and also give bounds for a simple, general technique for building geometric structures incrementally. One new algorithm reports all the intersecting pairs of a set of line segments in the plane, and requiresO(A+n logn) expected time, whereA is the number of intersecting pairs reported. The algorithm requiresO(n) space in the worst case. Another algorithm computes the convex hull ofn points inE ^d inO(n logn) expected time ford=3, andO(n ^[d/2]) expected time ford>3. The algorithm also gives fast expected times for random input points. Another algorithm computes the diameter of a set ofn points inE ³ inO(n logn) expected time, and on the way computes the intersection ofn unit balls inE ³. We show thatO(n logA) expected time suffices to compute the convex hull ofn points inE ³, whereA is the number of input points on the surface of the hull. Algorithms for halfspace range reporting are also given. In addition, we give asymptotically tight bounds for (k)-sets, which are certain halfspace partitions of point sets, and give a simple proof of Lee's bounds for high-order Voronoi diagrams.     

Efficient partition trees

We prove a theorem on partitioning point sets inE ^d (d fixed) and give an efficient construction of partition trees based on it. This yields a simplex range searching structure with linear space,O(n logn) deterministic preprocessing time, andO(n ^1?1/d (logn) ^O(1)) query time. WithO(nlogn) preprocessing time, where δ is an arbitrary positive constant, a more complicated data structure yields query timeO(n ^1?1/d (log logn) ^O(1)). This attains the lower bounds due to Chazelle [C1] up to polylogarithmic factors, improving and simplifying previous results of Chazelleet al. [CSW]. The partition result implies that, forr ^d≤n ^1?δ, a (1/r)-approximation of sizeO(r ^d) with respect to simplices for ann-point set inE ^d can be computed inO(n logr) deterministic time. A (1/r)-cutting of sizeO(r ^d) for a collection ofn hyperplanes inE ^d can be computed inO(n logr) deterministic time, provided thatr≤n ^1/(2d?1).     

The rigidity of Clifford torusS^1 \left( {\sqrt {\frac{1}{n}} } \right) \times S^{n - 1} \left( {\sqrt {\frac{{n - 1}}{n}} } \right)

In this paper, we prove that ifM is ann-dimensional closed minimal hypersurface with two distinct principal curvatures of a unit sphereS ⁿ⁺¹ (1), thenS=n andM is a Clifford torus ifn≤S≤n+[2n ²(n+4)/3(n(n+4)+4)], whereS is the squared norm of the second fundamental form ofM.     

The girth of a thin distance-regular graph

Let Γ be a distance-regular graph of diameterd≥3. For each vertexx of Γ, letT(x) denote the Terwilliger algebra for Γ with respect tox. An irreducibleT(x)-moduleW is said to bethin if dimE _i ^* (x)W≤1 for 0≤i≤d, whereE _i ^* (x) is theith dual idempotent for Γ with respect tox. The graph Γ isthin if for each vertexx of Γ, every irreducibleT(x)-module is thin. Aregular generalized quadrangle is a bipartite distance-regular graph with girth 8 and diameter 4. Our main results are as follows: Theorem. Let Γ=(X,R) be a distance-regular graph with diameter d≥3 and valency k≥3. Then the following are equivalent:

1. Γis a regular generalized quadrangle.
2. Γis thin and c ₃=1.

Corollary. Let Γ=(X,R) be a thin distance-regular graph with diameter d≥3 and valency k≥3. Then Γ has girth 3, 4, 6, or 8. Then girth of Γ is 8 exactly when Γ is a regular generalized quadrangle.     

On lines missing polyhedral sets in 3-space

We show some combinatorial and algorithmic results concerning finite sets of lines and terrains in 3-space. Our main results include:

1. An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of the set of lines that can be translated to infinity without intersecting a given finite set ofn lines, wherec is a suitable constant. This bound is almost tight.
2. AnO(n ^1.5+ε) randomized expected time algorithm that tests whether a directionv exists along which a set ofn red lines can be translated away from a set ofn blue lines without collisions. ε>0 is an arbitrary small but fixed constant.
3. An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of theenvelope of lines above a terrain withn edges, wherec is a suitable constant.
4. An algorithm for computing the intersection of two polyhedral terrains in 3-space withn total edges in timeO(n ^4/3+ε+k ^1/3 n ^1+ε+klog² n), wherek is the size of the output, and ε>0 is an arbitrary small but fixed constant. This algorithm improves on the best previous result of Chazelleet al. [5].

The tools used to obtain these results include Plücker coordinates of lines, random sampling, and polarity transformations in 3-space.     

Tilings of parallelograms with similar triangles

We say that a triangle δ tiles the polygonP ifP can be decomposed into finitely many non-overlapping triangles similar to δ. Let P bea parallelogram with anglesδ andπ -δ (0 <δ ≤π/2) and let δ be a triangle with anglesα, Β, γ (α ≤Β ≤γ). We prove that if δ tilesP then eitherδ ε α,Β,γ,π -γ, π - 2γ or dimL _P =dimL _δ. We also prove that for every parallelogramP, and for every integern (wheren≥ 2,n ? 3) there is a triangle δ so thatn similar copies of δ tileP.