3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects

We present a new data structure for a set of n convex simply-shaped fat objects in the plane, and use it to obtain efficient and rather simple solutions to several problems including (i) vertical ray shooting—preprocess a set of n non-intersecting convex simply-shaped flat objects in 3-space, whose xy-projections are fat, for efficient vertical ray shooting queries, (ii) point enclosure—preprocess a set C of n convex simply-shaped fat objects in the plane, so that the k objects containing a query point p can be reported efficiently, (iii) bounded-size range searching— preprocess a set C of n convex fat polygons, so that the k objects intersecting a “not-too-large” query polygon can be reported efficiently, and (iv) bounded-size segment shooting—preprocess a set C as in (iii), so that the first object (if exists) hit by a “not-too-long” oriented query segment can be found efficiently. For the first three problems we construct data structures of size O(λ_s(n)log³n), where s is the maximum number of intersections between the boundaries of the (xy-projections) of any pair of objects, and λ_s(n) is the maximum length of (n, s) Davenport-Schinzel sequences. The data structure for the fourth problem is of size O(λ_s(n)log²n). The query time in the first problem is O(log⁴n), the query time in the second and third problems is O(log³n + klog²n), and the query time in the fourth problem is O(log³n).

We also present a simple algorithm for computing a depth order for a set as in (i), that is based on the solution to the vertical ray shooting problem. (A depth order for , if exists, is a linear order of , such that, if K₁, K₂ and K₁ lies vertically above K₂, then K₁ precedes K₂.) Unlike the algorithm of Agarwal et al. (1995) that might output a false order when a depth order does not exist, the new algorithm is able to determine whether such an order exists, and it is often more efficient in practical situations than the former algorithm.     

Harmonic maps and 2-cycles, realizing the Thurston norm

Let be an oriented 3-manifold. We investigate when one of the fibers or a combination of fiber components, , of a harmonic map with Morse-type singularities delivers the Thurston norm of its homology class .

In particular, for a map with connected fibers and any well-positioned oriented surface in the homology class of a fiber, we show that the Thurston number satisfies an inequality

Here the variation is can be expressed in terms of the -invariants of the fiber components, and the twist measures the complexity of the intersection of with a particular set of ``bad" fiber components. This complexity is tightly linked with the optimal ``-height" of , being lifted to the -induced cyclic cover .

Based on these invariants, for any Morse map , we introduce the notion of its twist . We prove that, for a harmonic , if and only if .

     

On the degree of Hilbert polynomials associated to the torsion functor

Let be a local, Noetherian ring and an ideal. A question of Kodiyalam asks whether for fixed , the polynomial giving the th Betti number of has degree equal to the analytic spread of minus one. Under mild conditions on , we show that the answer is positive in a number of cases, including when is divisible by or is an integrally closed -primary ideal.

     

Pyramids in the complex projective plane

We study the critical points of the diameter functional on the n-fold Cartesian product of the complex projective plane C P ² with the Fubini-Study metric. Such critical points arise in the calculation of a metric invariant called the filling radius, and are akin to the critical points of the distance function. We study a special family of such critical points, P _kC P ¹C P ², k=1,2... We show that P _k is a local minimum of by verifying the positivity of the Hessian of (a smooth approximation to) at P _k. For this purpose, we use Shirokov's law of cosines and the holonomy of the normal bundle of C P ¹C P ². We also exhibit a critical point of , given by a subset which is not contained in any totally geodesic submanifold of C P ².     

Volume Contents

Volume Contents

Volume Contents     

Dynamic data structures for fat objects and their applications

We present several efficient dynamic data structures for point-enclosure queries, involving convex fat objects in or. Our planar structures are actually fitted for a more general class of objects – (β,δ)-covered objects – which are not necessarily convex, see definition below. These structures are more efficient than alternative known structures, because they exploit the fatness of the objects. We then apply these structures to obtain efficient solutions to two problems: (i) finding a perfect containment matching between a set of points and a set of convex fat objects, and (ii) finding a piercing set for a collection of convex fat objects, whose size is optimal up to some constant factor.     

Extended Rees algebras and mixed multiplicities

Partially supported by the general research fund at the University of Kansas     

Free products of kω-topological groups with normal amalgamation

It is shown in this paper that if A is a closed normal subgroup of k_ω-topological groups G and H, then the free product of G and H with A amalgamated, G1_AH, exists, is Hausdorff and indeed a k_ω-group.