Computing the Shortest Essential Cycle

An essential cycle on a surface is a simple cycle that cannot be continuously deformed to a point or a single boundary. We describe algorithms to compute the shortest essential cycle in an orientable combinatorial surface in O(n ²log n) time, or in O(nlog n) time when both the genus and number of boundaries are fixed. Our results correct an error in a paper of Erickson and Har-Peled (Discrete Comput. Geom. 31(1):37–59, 2004).     

Improved algorithms for the multicut and multiflow problems in rooted trees

Costa et al. (Oper. Res. Lett. 31:21–27, 2003) presented a quadratic O(min (Kn,n ²)) greedy algorithm to solve the integer multicut and multiflow problems in a rooted tree. (n is the number of nodes of the tree, and K is the number of commodities). Their algorithm is a special case of the greedy type algorithm of Kolen (Location problems on trees and in the rectilinear plane. Ph.D. dissertation, 1982) to solve weighted covering and packing problems defined by general totally balanced (greedy) matrices. In this communication we improve the complexity bound in Costa et al. (Oper. Res. Lett. 31:21–27, 2003) and show that in the case of the integer multicut and multiflow problems in a rooted tree the greedy algorithm of Kolen can be implemented in subquadratic O(K+n+min (K,n)log n) time. The improvement is obtained by identifying additional properties of this model which lead to a subquadratic transformation to greedy form and using more sophisticated data structures.      

Computing homotopic shortest paths in the plane

We address the problem of computing homotopic shortest paths in the presence of obstacles in the plane. Problems on homotopy of paths received attention very recently [Cabello et al., in: Proc. 18th Annu. ACM Sympos. Comput. Geom., 2002, pp. 160–169; Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. We present two output-sensitive algorithms, for simple paths and non-simple paths. The algorithm for simple paths improves the previous algorithm [Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. The algorithm for non-simple paths achieves O(log²n) time per output vertex which is an improvement by a factor of O(n/log²n) of the previous algorithm [Hershberger, Snoeyink, Comput. Geom. Theory Appl. 4 (1994) 63–98], where n is the number of obstacles. The running time has an overhead O(n²⁺) for any positive constant . In the case k<n²⁺, where k is the total size of the input and output, we improve the running to O((n+k+(nk)^2/3)log^O(1)n).     

Efficient Algorithms for Maximum Regression Depth

We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes. An O(n ^d ) time and O(n ^d−1) space algorithm computes undirected depth of all points in d dimensions. Properties of undirected depth lead to an O(nlog ² n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions, which has been improved to an O(nlog n) time algorithm by Langerman and Steiger (Discrete Comput. Geom. 30(2):299–309, [2003]). Furthermore, we describe the structure of depth in the plane and higher dimensions, leading to various other geometric and algorithmic results. A preliminary version of this paper appeared in the proceedings of the 15th Annual ACM Symposium on Computational Geometry (1999) M. van Kreveld partially funded by the Netherlands Organization for Scientific Research (NWO) under FOCUS/BRICKS grant number 642.065.503. J.S.B. Mitchell’s research largely conducted while the author was a Fulbright Research Scholar at Tel Aviv University. The author is partially supported by NSF (CCR-9504192, CCR-9732220), Boeing, Bridgeport Machines, Sandia, Seagull Technology, and Sun Microsystems. M. Sharir supported by NSF Grants CCR-97-32101 and CCR-94-24398, by grants from the U.S.–Israeli Binational Science Foundation, the G.I.F., the German–Israeli Foundation for Scientific Research and Development, and the ESPRIT IV LTR project No. 21957 (CGAL), and by the Hermann Minkowski—MINERVA Center for Geometry at Tel Aviv University. J. Snoeyink supported in part by grants from NSERC, the Killam Foundation, and CIES while at the University of British Columbia.     

Dynamic Coresets

We give a dynamic data structure that can maintain an ε-coreset of n points, with respect to the extent measure, in O(log n) time per update for any constant ε>0 and any constant dimension. The previous method by Agarwal, Har-Peled, and Varadarajan requires polylogarithmic update time. For points with integer coordinates bounded by U, we alternatively get O(log log U) time. Numerous applications follow, for example, on dynamically approximating the width, smallest enclosing cylinder, minimum bounding box, or minimum-width annulus. We can also use the same approach to maintain approximate k-centers in time O(log n) (or O(log log U) if the spread is bounded by U) for any constant k and any constant dimension. For the smallest enclosing cylinder problem, we also show that a constant-factor approximation can be maintained in O(1) randomized amortized time on the word RAM. This work has been supported by NSERC. A preliminary version of this paper has appeared in Proc. 24th ACM Sympos Comput. Geom., 2008.     

Some Exponential Inequalities for Positively Associated Random Variables and Rates of Convergence of the Strong Law of Large Numbers

We present some exponential inequalities for positively associated unbounded random variables. By these inequalities, we obtain the rate of convergence n ^−1/2 β _n log ^3/2 n in which β _n can be particularly taken as (log log n)^1/σ with any σ>2 for the case of geometrically decreasing covariances, which is faster than the corresponding one n ^−1/2(log log n)^1/2log ² n obtained by Xing, Yang, and Liu in J. Inequal. Appl., doi: (2008) for the case mentioned above, and derive the convergence rate n ^−1/2 β _n log ^1/2 n for the above β _n under the given covariance function, which improves the relevant one n ^−1/2(log log n)^1/2log n obtained by Yang and Chen in Sci. China, Ser. A 49(1), 78–85 (2006) for associated uniformly bounded random variables. In addition, some moment inequalities are given to prove the main results, which extend and improve some known results.     

On Order Types of Systems of Segments in the Plane

Let r(n) denote the largest integer such that every family C\mathcal{C} of n pairwise disjoint segments in the plane in general position has r(n) members whose order type can be represented by points. Pach and Tóth gave a construction that shows r(n) < n ^log8/log9 (Pach and Tóth 2009). They also stated that one can apply the Erdős–Szekeres theorem for convex sets in Pach and Tóth (Discrete Comput Geom 19:437–445, 1998) to obtain r(n) > log₁₆ n. In this note, we will show that r(n) > cn ^1/4 for some absolute constant c.     

FFTs on the Rotation Group

We discuss an implementation of an efficient algorithm for the numerical computation of Fourier transforms of bandlimited functions defined on the rotation group SO(3). The implementation is freely available on the web. The algorithm described herein uses O(B ⁴) operations to compute the Fourier coefficients of a function whose Fourier expansion uses only (the O(B ³)) spherical harmonics of degree at most B. This compares very favorably with the direct O(B ⁶) algorithm derived from a basic quadrature rule on O(B ³) sample points. The efficient Fourier transform also makes possible the efficient calculation of convolution over SO(3) which has been used as the analytic engine for some new approaches to searching 3D databases (Funkhouser et al., ACM Trans. Graph. 83–105, [2003]; Kazhdan et al., Eurographics Symposium in Geometry Processing, pp. 167–175, [2003]). Our implementation is based on the “Separation of Variables” technique (see, e.g., Maslen and Rockmore, Proceedings of the DIMACS Workshop on Groups and Computation, pp. 183–237, [1997]). In conjunction with techniques developed for the efficient computation of orthogonal polynomial expansions (Driscoll et al., SIAM J. Comput. 26(4):1066–1099, [1997]), our fast SO(3) algorithm can be improved to give an algorithm of complexity O(B ³log ² B), but at a cost in numerical reliability. Numerical and empirical results are presented establishing the empirical stability of the basic algorithm. Examples of applications are presented as well. First author was supported by NSF ITR award; second author was supported by NSF Grant 0219717 and the Santa Fe Institute.     

A Full-Newton Step Infeasible Interior-Point Algorithm for Linear Programming Based on a Kernel Function

This paper proposes an infeasible interior-point algorithm with full-Newton step for linear programming, which is an extension of the work of Roos (SIAM J. Optim. 16(4):1110–1136, 2006). The main iteration of the algorithm consists of a feasibility step and several centrality steps. We introduce a kernel function in the algorithm to induce the feasibility step. For parameter p∈[0,1], the polynomial complexity can be proved and the result coincides with the best result for infeasible interior-point methods, that is, O(nlog n/ε). This work was supported in part by the National Natural Science Foundation of China under Grant No. 10871098.     

Optimal Partition Trees

We revisit one of the most fundamental classes of data structure problems in computational geometry: range searching. Matoušek (Discrete Comput. Geom. 10:157–182, 1993) gave a partition tree method for d-dimensional simplex range searching achieving O(n) space and O(n ^1−1/d ) query time. Although this method is generally believed to be optimal, it is complicated and requires O(n ^1+ε ) preprocessing time for any fixed ε>0. An earlier method by Matoušek (Discrete Comput. Geom. 8:315–334, 1992) requires O(nlogn) preprocessing time but O(n ^1−1/d log ^O(1) n) query time. We give a new method that achieves simultaneously O(nlogn) preprocessing time, O(n) space, and O(n ^1−1/d ) query time with high probability. Our method has several advantages:

Orders on Multisets and Discrete Cones

We study additive representability of orders on multisets (of size k drawn from a set of size n) which satisfy the condition of independence of equal submultisets (IES) introduced by Sertel and Slinko (Ranking committees, words or multisets. Nota di Laboro 50.2002. Center of Operation Research and Economics. The Fundazione Eni Enrico Mattei, Milan, 2002, Econ. Theory 30(2):265–287, 2007). Here we take a geometric view of those orders, and relate them to certain combinatorial objects which we call discrete cones. Following Fishburn (J. Math. Psychol., 40:64–77, 1996) and Conder and Slinko (J. Math. Psychol., 48(6):425–431, 2004), we define functions f(n,k) and g(n,k) which measure the maximal possible deviation of an arbitrary order satisfying the IES and an arbitrary almost representable order satisfying the IES, respectively, from a representable order. We prove that g(n,k) = n − 1 whenever n ≥ 3 and (n, k) ≠ (5, 2). In the exceptional case, g(5,2) = 3. We also prove that g(n,k) ≤ f(n,k) ≤ n and establish that for small n and k the functions g(n,k) and f(n,k) coincide.      

On the Union of Cylinders in Three Dimensions

We show that the combinatorial complexity of the union of n infinite cylinders in ℝ³, having arbitrary radii, is O(n ^2+ε ), for any ε>0; the bound is almost tight in the worst case, thus settling a conjecture of Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000), who established a nearly-quadratic bound for the restricted case of nearly congruent cylinders. Our result extends, in a significant way, the result of Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000), in particular, a simple specialization of our analysis to the case of nearly congruent cylinders yields a nearly-quadratic bound on the complexity of the union in that case, thus significantly simplifying the analysis in Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000). Finally, we extend our technique to the case of “cigars” of arbitrary radii (that is, Minkowski sums of line-segments and balls) and show that the combinatorial complexity of the union in this case is nearly-quadratic as well. This problem has been studied in Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000) for the restricted case where all cigars have (nearly) equal radii. Based on our new approach, the proof follows almost verbatim from the analysis for infinite cylinders and is significantly simpler than the proof presented in Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000).     

Kinetic Spanners in ℝ<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>

We present a new (1+ε)-spanner for sets of n points in ℝ ^d . Our spanner has size O(n/ε ^d−1) and maximum degree O(log  ^d n). The main advantage of our spanner is that it can be maintained efficiently as the points move: Assuming that the trajectories of the points can be described by bounded-degree polynomials, the number of topological changes to the spanner is O(n ²/ε ^d−1), and using a supporting data structure of size O(nlog  ^d n), we can handle events in time O(log  ^d+1 n). Moreover, the spanner can be updated in time O(log n) if the flight plan of a point changes. This is the first kinetic spanner for points in ℝ ^d whose performance does not depend on the spread of the point set.     

A Bichromatic Incidence Bound and an Application

We prove a new, tight upper bound on the number of incidences between points and hyperplanes in Euclidean d-space. Given n points, of which k are colored red, there are O _d (m ^2/3 k ^2/3 n ^(d−2)/3+kn ^d−2+m) incidences between the k red points and m hyperplanes spanned by all n points provided that m=Ω(n ^d−2). For the monochromatic case k=n, this was proved by Agarwal and Aronov (Discrete Comput. Geom. 7(4):359–369, 1992).     

The negative cycles polyhedron and hardness of checking some polyhedral properties

Given a graph G=(V,E) and a weight function on the edges w:E→ℝ, we consider the polyhedron P(G,w) of negative-weight flows on G, and get a complete characterization of the vertices and extreme directions of P(G,w). Based on this characterization, and using a construction developed in Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008), we show that, unless P=NP, there is no output polynomial-time algorithm to generate all the vertices of a 0/1-polyhedron. This strengthens the NP-hardness result of Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008) for non 0/1-polyhedra, and comes in contrast with the polynomiality of vertex enumeration for 0/1-polytopes (Bussiech and Lübbecke in Comput. Geom., Theory Appl. 11(2):103–109, 1998). As further applications, we show that it is NP-hard to check if a given integral polyhedron is 0/1, or if a given polyhedron is half-integral. Finally, we also show that it is NP-hard to approximate the maximum support of a vertex of a polyhedron in ℝ ⁿ within a factor of 12/n.     

Decremental Dynamic Connectivity

We consider Las Vegas randomized dynamic algorithms for on-line connectivity problems with deletions only. In particular, we show that starting from a graph with m edges and n nodes, we can maintain a spanning forest during m deletions in O(m log(n²/m) + n(log n)³(log log n)²) expected time, which is O(m) if m = Θ(n²) and O(m log n) if m = Ω(n(log n log log n)²). The deletions may be interspersed with connectivity queries, each of which is answered in constant time. The previous best bound was O(m log² n) by Henzinger and Thorup which covered both insertions and deletions. The result is based on a general randomized reduction for edge connectivity problems of many deletions-only queries to a few deletions and insertions queries. For 2-edge connectivity, the complexity is improved from O(m(log n)⁵) to O(m log(n²/m) + n(log n)⁶(log log n)²). For the general decremental k-edge-connectivity problem, we get a total running time of O(k²n² polylog n). Here the previous best bound was O(kmn polylog n). Improved running times are also achieved for the static consensus tree problem, with applications to computational biology and relational data bases.     

Enumerating K best paths in length order in DAGs

We address the problem of finding the K best paths connecting a given pair of nodes in a directed acyclic graph (DAG) with arbitrary lengths. One of the main results in this paper is the proof that a tree representing the kth shortest path is obtained by an arc exchange in one of the previous (k − 1) trees (each of which contains a previous best path). An O(m + K(n + log K)) time and O(K + m) space algorithm is designed to explicitly determine the K shortest paths in a DAG with n nodes and m arcs. The algorithm runs in O(m + Kn) time using O(K + m) space in DAGs with integer length arcs. Empirical results confirming the superior performance of the algorithm to others found in the literature for randomly generated graphs are reported.     

An Optimal-Time Algorithm for Shortest Paths on Realistic Polyhedra

We generalize our optimal-time algorithm for computing (an implicit representation of) the shortest-path map from a fixed source s on the surface of a convex polytope P to three realistic scenarios where P is a possibly nonconvex polyhedron. In the first scenario, ∂ P is a terrain whose maximum facet slope is bounded by any fixed constant. In the second scenario, P is an uncrowded polyhedron—each axis-parallel square h of side length l(h) whose smallest Euclidean distance to a vertex of P is at least l(h) is intersected by at most O(1) facets of ∂ P—an input model which, as we show, is a generalization of the well-known low-density model. In the third scenario, P is self-conforming—here, for each edge e of P, there is a connected region R(e) of O(1) facets whose union contains e, so that the shortest path distance from e to any edge e′ of ∂ R(e) is at least c⋅max {|e|,|e′|}, where c is some positive constant. In particular, it includes the case where each facet of ∂ P is fat and each vertex is incident to at most O(1) facets of ∂ P. In all the above cases the algorithm runs in O(nlog n) time and space, where n is the number of edges of P, and produces an implicit representation of the shortest-path map, so that the shortest path from s to any query point q can be determined in O(log n) time. The constants of proportionality depend on the various parameters (maximum facet slope, crowdedness, etc.). We also note that the self-conforming model allows for a major simplification of the algorithm.     

O(dlog?N)-Quantics Approximation of N-d Tensors in High-Dimensional Numerical Modeling

In the present paper, we discuss the novel concept of super-compressed tensor-structured data formats in high-dimensional applications. We describe the multifolding or quantics-based tensor approximation method of O(dlog N)-complexity (logarithmic scaling in the volume size), applied to the discrete functions over the product index set {1,…,N}^⊗d , or briefly N-d tensors of size N ^d , and to the respective discretized differential-integral operators in ℝ ^d . As the basic approximation result, we prove that a complex exponential sampled on an equispaced grid has quantics rank 1. Moreover, a Chebyshev polynomial, sampled over a Chebyshev Gauss–Lobatto grid, has separation rank 2 in the quantics tensor format, while for the polynomial of degree m over a Chebyshev grid the respective quantics rank is at most 2m+1. For N-d tensors generated by certain analytic functions, we give a constructive proof of the O(dlog Nlog ε ⁻¹)-complexity bound for their approximation by low-rank 2-(dlog N) quantics tensors up to the accuracy ε>0. In the case ε=O(N ^−α ), α>0, our approach leads to the quantics tensor numerical method in dimension d, with the nearly optimal asymptotic complexity O(d/αlog ² ε ⁻¹). From numerical examples presented here, we observe that the quantics tensor method has proved its value in application to various function related tensors/matrices arising in computational quantum chemistry and in the traditional finite element method/boundary element method (FEM/BEM). The tool apparently works.     

Iterative methods based on the signum function approach for solving nonlinear equations

For finding a root of an equation f(x) = 0 on an interval (a, b), we develop an iterative method using the signum function and the trapezoidal rule for numerical integrations based on the recent work (Yun, Appl Math Comput 198:691–699, 2008). This method, so-called signum iteration method, depends only on the signum function sgn(f(x)){\rm{sgn}}\left(f(x)\right) independently of the behavior of f(x), and the error bound of the kth approximation is (b − a)/(2N ^k ), where N is the number of integration points for the trapezoidal rule in each iteration. In addition we suggest hybrid methods which combine the signum iteration method with usual methods such as Newton, Ostrowski and secant methods. In particular the hybrid method combined with the signum iteration and the secant method is a predictor-corrector type method (Noor and Ahmad, Appl Math Comput 180:167–172, 2006). The proposed methods result in the rapidly convergent approximations, without worry about choosing a proper initial guess. By some numerical examples we show the superiority of the presented methods over the existing iterative methods.