Selecting distances in arrangements of hyperplanes spanned by points

In this paper we consider a problem of distance selection in the arrangement of hyperplanes induced by n given points. Given a set of n points in d-dimensional space and a number k, , determine the hyperplane that is spanned by d points and at distance ranked by k from the origin. For the planar case we present an O(nlog²n) runtime algorithm using parametric search partly different from the usual approach [N. Megiddo, J. ACM 30 (1983) 852]. We establish a connection between this problem in 3-d and the well-known 3SUM problem using an auxiliary problem of counting the number of vertices in the arrangement of n planes that lie between two sheets of a hyperboloid. We show that the 3-d problem is almost 3SUM-hard and solve it by an O(n²log²n) runtime algorithm. We generalize these results to the d-dimensional (d4) space and consider also a problem of enumerating distances.     

k-Plane Clustering

A finite new algorithm is proposed for clustering m given points in n-dimensional real space into k clusters by generating k planes that constitute a local solution to the nonconvex problem of minimizing the sum of squares of the 2-norm distances between each point and a nearest plane. The key to the algorithm lies in a formulation that generates a plane in n-dimensional space that minimizes the sum of the squares of the 2-norm distances to each of m₁ given points in the space. The plane is generated by an eigenvector corresponding to a smallest eigenvalue of an n × n simple matrix derived from the m₁ points. The algorithm was tested on the publicly available Wisconsin Breast Prognosis Cancer database to generate well separated patient survival curves. In contrast, the k-mean algorithm did not generate such well-separated survival curves.     

Generalized dynamic programming methods in integer programming

When regarded as a shortest route problem, an integer program can be seen to have a particularly simple structure. This allows the development of an algorithm for finding thek ^th best solution to an integer programming problem with max{O(kmn), O(k logk)} operations. Apart from its value in the parametric study of an optimal solution, the approach leads to a general integer programming algorithm consisting of (1) problem relaxation, (2) solution of the relaxed problem parametrically by dynamic programming, and (3) generation ofk ^th best solutions until a feasible solution is found. Elementary methods based on duality for reducingk for a given problem relaxation are then outlined, and some examples and computational aspects are discussed.     

K-Levels of Concave Surfaces

Abstract. We show that for any line l in space, there are at most k(k+1) tangent planes through l to the k -level of an arrangement of concave surfaces. This is a generalization of Lovász's lemma, which is a key constituent in the analysis of the complexity of k -levels of planes. Our proof is constructive, and finds a family of concave surfaces covering the ``laminated at-most-k -level.' As a consequence, (1) we have an O((n-k) ^2/3 n ² ) upper bound for the complexity of the k -level of n triangles of space, and (2) we can extend the k -set result in space to the k -set of a system of subsets of n points.     

Streaming Algorithms for Line Simplification

We study the following variant of the well-known line-simplification problem: we are getting a (possibly infinite) sequence of points p ₀,p ₁,p ₂,… in the plane defining a polygonal path, and as we receive the points, we wish to maintain a simplification of the path seen so far. We study this problem in a streaming setting, where we only have a limited amount of storage, so that we cannot store all the points. We analyze the competitive ratio of our algorithms, allowing resource augmentation: we let our algorithm maintain a simplification with 2k (internal) points and compare the error of our simplification to the error of the optimal simplification with k points. We obtain the algorithms with O(1) competitive ratio for three cases: convex paths, where the error is measured using the Hausdorff distance (or Fréchet distance), xy-monotone paths, where the error is measured using the Hausdorff distance (or Fréchet distance), and general paths, where the error is measured using the Fréchet distance. In the first case the algorithm needs O(k) additional storage, and in the latter two cases the algorithm needs O(k ²) additional storage.     

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.     

Traversing Layered Graphs Using the Work Function Algorithm

The work function algorithm (WFA) is an on-line algorithm that has been studied mostly in connection with thek-server problem, but can actually be used on a wide variety of on-line problems. Despite being a simple algorithm, WFA has proven to be difficult to analyze, and until recently few interesting results were known. We analyze the performance of the generalized work function algorithm, denoted α-WFA, for on-line traversal of layered graphs. We show that for layered graphs of widthkand any α>1, α-WFA achieves competitive ratio (α+1)(2α/(α−1))^k−1−α. This gives anO(k2^k)-competitive ratio for appropriate choice of α, improving the previous upper bound ofO(k³2^k).     

Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem

The dynamic programming algorithm of [12.] for the bandwidth minimization problem is improved. It is shown that, for all k > 1, BANDWIDTH(k) can be solved in O(n^k) steps and simultaneous O(n^k) space, where n is the number of vertices in the graph, and that each such problem is in NSPACE(log n). The same improved dynamic programming algorithm approach works to show that the MINCUT LINEAR ARRANGEMENT problem restricted to the fixed value k, denoted by MINCUT(k), is solvable in O(n^k) steps and simultaneous O(n^k) space and is in the class NSPACE(log n).     

A note onC o Galerkin methods for two-point boundary problems

Summary As is known [4]. theC ^o Galerkin solution of a two-point boundary problem using piecewise polynomial functions, hasO(h ^2k ) convergence at the knots, wherek is the degree of the finite element space. Also, it can be proved [5] that at specific interior points, the Gauss-Legendre points the gradient hasO(h ^k+1) convergence, instead ofO(h ^k ). In this note, it is proved that on any segment there arek–1 interior points where the Galerkin solution is ofO(h ^k+2), one order better than the global order of convergence. These points are the Lobatto points.     

The <Emphasis Type="Italic">k</Emphasis>-Centrum Straight-line Location Problem

A line is sought in the plane which minimizes the sum of the k largest (Euclidean) weighted distances from n given points. This problem generalizes the known straight-line center and median problems and, as far as the authors are aware, has not been tackled up to now. By way of geometric duality it is shown that such a line may always be found which either passes through two of the given points or lying at equal weighted distance from three of these. This allows construction of an algorithm to find all t-centrum lines for 1 ≤ t ≤ k in O((k + logn)n ³). Finally it is shown that both, the characterization of an optimal line and the algorithm, can be extended to any smooth norm.     

An efficient fixed-parameter algorithm for 3-Hitting Set

Given a collection C of subsets of size three of a finite set S and a positive integer k, the 3-Hitting Set problem is to determine a subset S′S with |S′|k, so that S′ contains at least one element from each subset in C. The problem is NP-complete, and is motivated, for example, by applications in computational biology. Improving previous work, we give an O(2.270^k+n) time algorithm for 3-Hitting Set, which is efficient for small values of k, a typical occurrence in some applications. For d-Hitting Set we present an O(c^k+n) time algorithm with c=d−1+O(d⁻¹).     

Exceptional directions for a convex body

Let K be a convex body in Rⁿ andO be a point inside K. We examine the Grassmann manifold of k-planes passing throughO. We take as exceptional the planes intersecting K along a body having at least one (k – 1)-dimensional face such that it does not have points inside the hyperfaces of body K. We prove that in the Grassmann manifold G _k ⁿ the set of such exceptional planes is of measure zero.Translated from Matematicheskie Zametki, Vol. 20, No. 3, pp. 365–371, September, 1976.The author thanks V. A. Zalgaller for aid and advice on the work.     

A fast algorithm for computing minimum 3-way and 4-way cuts

For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k=3,4. The algorithm runs in O(n ^k-1 F(n,m))=O(mn ^k log(n ² /m)) time and O(n ²) space for k=3,4, where F(n,m) denotes the time bound required to solve the maximum flow problem in G. The bound for k=3 matches the current best deterministic bound ?(mn ³) for weighted graphs, but improves the bound ?(mn ³) to O(n ² F(n,m))=O(min{mn ^8/3,m ^3/2 n ²}) for unweighted graphs. The bound ?(mn ⁴) for k=4 improves the previous best randomized bound ?(n ⁶) (for m=o(n ²)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system. Received: April 1999 / Accepted: February 2000?Published online August 18, 2000     

An Efficient Algorithm for Finding a Maximum Weight k-Independent Set on Trapezoid Graphs

The maximum weight k-independent set problem has applications in many practical problems like k-machines job scheduling problem, k-colourable subgraph problem, VLSI design layout and routing problem. Based on DAG (Directed Acyclic Graph) approach, an O(kn ²) time sequential algorithm is designed in this paper to solve the maximum weight k-independent set problem on weighted trapezoid graphs. The weights considered here are all non-negative and associated with each of the n vertices of the graph.     

On geometric optimization with few violated constraints

We investigate the problem of finding the best solution satisfying all butk of the given constraints, for an abstract class of optimization problems introduced by Sharir and Welzl—the so-calledLP-type problems. We give a general algorithm and discuss its efficient implementations for specific geometric problems. For instance for the problem of computing the smallest circle enclosing all butk of the givenn points in the plane, we obtain anO(n logn+k ³ n ^ε) algorithm; this improves previous results fork small compared withn but moderately growing. We also establish some results concerning general properties ofLP-type problems. This research was supported in part by Charles University Grant No. 351 and Czech Republic Grant GAČR 201/93/2167. Part of this research was performed while the author was visting the Computer Science Institute, Free University Berlin, and it was supported by the German-Israeli Foundation of Scientific Research and Development (G.I.F.), and part while visiting the Max-Planck Institute for Computer Science in Saarbrücken.     

Configurations Maximizing the Number of Pairs of Hamming-Adjacent Lattice Points

The following question is considered: Which sets of k lattice points among the n^d points in a d-dimensional cube of length n maximize the number of pairs of points differing in only one coordinate? It is shown that maximal configurations for any (d, n, k) are obtained by choosing the first k points in a lexicographic ordering of the points by coordinates. Some possible generalizations of the problem are discussed.     

Approximation of multivariable functions with respect to random points less than 2 k,k dimension of space

Summary The problem of the numerical approximation of multivariable functions has been solved by the Monte Carlo method when the data points are assumed to be given on discrete lattice points [5, 8, 2]. When the data points are randomly distributed and very numerous there are some results in the literature [3, 6] but if the number of the points is less than 2 ^k , wherek is the dimension of the space, it is very difficult to develop approximation formulas. This paper gives a solution to this problem by local approximations.     

Increasing the Weight of Minimum Spanning Trees

The problems of computing the maximum increase in the weight of the minimum spanning trees of a graph caused by the removal of a given number of edges, or by finite increases in the weights of the edges, are investigated. For the case of edge removals, the problem is shown to be NP-hard and an Ω(1/log k)-approximation algorithm is presented for it, where (input parameter) k > 1 is the number of edges to be removed. The second problem is studied, assuming that the increase in the weight of an edge has an associated cost proportional to the magnitude of the change. An O(n³m² log(n²/m)) time algorithm is presented to solve it.     

Criteria of the <Emphasis Type="Italic">k</Emphasis>-singularity and division of 1-singular systems

The concept of the k-singularity of systems of points in ℝ ^m space with l ₁ metrics is studied. A system of q points is k-singular if and only if the dimensionality of the linear space of polynomials with powers no higher than the k of the columns of the matrix of pair-wise distances (element-wise multiplication) is strictly less than q. An algebraic criterion of k-singularity is obtained. The problem of dividing a system of points into subsystems that are not 1-singular is considered. An estimate of the minimum number of such subsystems is obtained.     

The Cohomology Ring of Weight Varieties and Polygon Spaces

We use a theorem of S. Tolman and J. Weitsman (The cohomology rings of Abelian symplectic quotients, math. DG/9807173) to find explicit formulæ for the rational cohomology rings of the symplectic reduction of flag varieties in ⁿ, or generic coadjoint orbits of SU(n), by (maximal) torus actions. We also calculate the cohomology ring of the moduli space of n points in P^k, which is isomorphic to the Grassmannian of k planes in ⁿ, by realizing it as a degenerate coadjoint orbit.