Polynomial-time approximation schemes for packing and piercing fat objects

We consider two problems: given a collection of n fat objects in a fixed dimension, (1) ( packing) find the maximum subcollection of pairwise disjoint objects, and (2) ( piercing) find the minimum point set that intersects every object. Recently, Erlebach, Jansen, and Seidel gave a polynomial-time approximation scheme (PTAS) for the packing problem, based on a shifted hierarchical subdivision method. Using shifted quadtrees, we describe a similar algorithm for packing but with a smaller time bound. Erlebach et al.'s algorithm requires polynomial space. We describe a different algorithm, based on geometric separators, that requires only linear space. This algorithm can also be applied to piercing, yielding the first PTAS for that problem.     

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.     

Ray shooting and intersection searching amidst fat convex polyhedra in 3-space

We present a data structure for ray-shooting queries in a set of convex fat polyhedra of total complexity n in . The data structure uses O(n^2+ε) storage and preprocessing time, and queries can be answered in O(log²n) time. A trade-off between storage and query time is also possible: for any m with n<m<n², we can construct a structure that uses O(m^1+ε) storage and preprocessing time such that queries take time.We also describe a data structure for simplex intersection queries in a set of n convex fat constant-complexity polyhedra in . For any m with n<m<n³, we can construct a structure that uses O(m^1+ε) storage and preprocessing time such that all polyhedra intersecting a query simplex can be reported in O((n/m^1/3)logn+k) time, where k is the number of answers.     

Dynamic shortest paths and transitive closure: Algorithmic techniques and data structures

In this paper, we survey fully dynamic algorithms for path problems on general directed graphs. In particular, we consider two fundamental problems: dynamic transitive closure and dynamic shortest paths. Although research on these problems spans over more than three decades, in the last couple of years many novel algorithmic techniques have been proposed. In this survey, we will make a special effort to abstract some combinatorial and algebraic properties, and some common data-structural tools that are at the base of those techniques. This will help us try to present some of the newest results in a unifying framework so that they can be better understood and deployed also by non-specialists.     

Homogenization and concentrated capacity for the heat equation with non-linear variational data in reticular almost disconnected structures and applications to visual transduction

Out of a right, circular cylinder of height H and cross-section a disc of radius R+ one removes a stack of nH/ parallel, equi-spaced cylinders C_j,j=1,2,...,n, each of radius R and height . Here , are fixed positive numbers and is a positive parameter to be allowed to go to zero. The union of the C_j almost fills in the sense that any two contiguous cylinders C_j are at a mutual distance of the order of and that the outer shell, i.e., the gap S=-_o has thickness of the order of (_o is obtained from by formally setting =0). The cylinder from which the C_j are removed, is an almost disconnected structure, it is denoted by , and it arises in the mathematical theory of phototransduction.For each >0 we consider the heat equation in the almost disconnected structure , for the unknown function u, with variational boundary data on the faces of the removed cylinders C_j. The limit of this family of problems as 0 is computed by concentrating heat capacity and diffusivity on the outer shell, and by homogenizing the u within the limiting cylinder _o.It is shown that the limiting problem consists of an interior diffusion in _o and a boundary diffusion on the lateral boundary S of _o. The interior diffusion is governed by the 2-dimensional heat equation in _o, for an interior limiting function u. The boundary diffusion is governed by the Laplace–Beltrami heat equation on S, for a boundary limiting function u_S. Moreover the exterior flux of the interior limit u provides the source term for the boundary diffusion on S. Finally the interior limit u, computed on S in the sense of the traces, coincides with the boundary limit u_S. As a consequence of the geometry of , local arguments do not suffice to prove convergence in _o, and also we have to take into account the behavior of the solution in S. A key, novel idea consists in extending equi-bounded and equi-Hölder continuous functions in -dependent domains, into equi-bounded and equi-Hölder continuous functions in the whole ^N, by means of the Kirzbraun–Pucci extension technique.The biological origin of this problem is traced, and its application to signal transduction in the retina rod cells of vertebrates is discussed. Mathematics Subject Classification (2000) 35B27, 35K50, 92C37     

Pseudo-orthogonality for graph 1-Laplacian eigenvectors and applications to higher Cheeger constants and data clustering

The data clustering problem consists in dividing a data set into prescribed groups of homogeneous data. This is an NP-hard problem that can be relaxed in the spectral graph theory, where the optimal cuts of a graph are related to the eigenvalues of graph 1-Laplacian. In this paper, we first give new notations to describe the paths, among critical eigenvectors of the graph 1-Laplacian, realizing sets with prescribed genus. We introduce the pseudo-orthogonality to characterize m₃(G), a special eigenvalue for the graph 1-Laplacian. Furthermore, we use it to give an upper bound for the third graph Cheeger constant h₃(G), that is, h₃(G) 6 m₃(G). This is a first step for proving that the k-th Cheeger constant is the minimum of the 1-Laplacian Raylegh quotient among vectors that are pseudo-orthogonal to the vectors realizing the previous k - 1 Cheeger constants. Eventually, we apply these results to give a method and a numerical algorithm to compute m₃(G), based on a generalized inverse power method.     

Systematic data generation and test design for solution algorithms on the example of SALBPGen for assembly line balancing

Recently, the importance of correctly designed computational experiments for testing algorithms has been a subject of extended discussions. Whenever real-world data is lacking, generated data sets provide a substantive methodological tool for experiments. Focused research questions need to base on specialized, randomized and sufficiently large data sets, which are sampled from the population of interest. We integrate the generation of data sets into the process of scientific testing.