Evaluating Network Reliability and 2-Edge-Connected Reliability in Linear Time for Bounded Pathwidth Graphs

This paper presents a decomposition method for computing the 2-edge-connected reliability of undirected networks. This reliability is defined as the probability that all the vertices of a given graph G are 2-edge-connected, when edges fail independently with known probabilities. The principle of this method was introduced by Rosenthal in 1977 [1]. For the all terminal reliability problem it consists in enumerating specific state classes of some subnetworks. These classes are represented by the partitions of the boundary sets. For the 2-edge-connected reliability problem these classes are represented by labeled forests whose nodes are the partition blocks and some ``unidentified' blocks. Our implementation uses a vertex linear ordering. The computational complexity depends on the number of classes, which depends on the vertex separation number of a given vertex linear ordering. Our computational results show the efficiency of this method when the vertex separation number is smaller than 7.     

A method for solving the n-dimensional convex hull problem

A method is presented for finding all vertices and all hyperplanes containing the faces of a convex polyhedron spanned by a given finite set X in Euclidean space Eⁿ. The present paper indicates how this method can be applied to the investigation of linear separability of two given finite sets X₁ and X₂ in Eⁿ. In the case of linear separability of these sets the proposed method makes it possible to find the separating hyperplane.     

Capacity-Constrained Delaunay Triangulation for point distributions

Sample point distributions possessing blue noise spectral characteristics play a central role in computer graphics, but are notoriously difficult to generate. We describe an algorithm to very efficiently generate these distributions. The core idea behind our method is to compute a Capacity-Constrained Delaunay Triangulation (CCDT), namely, given a simple polygon P in the plane, and the desired number of points n, compute a Delaunay triangulation of the interior of P with n Steiner points, whose triangles have areas which are as uniform as possible. This is computed iteratively by alternating update of the point geometry and triangulation connectivity. The vertex set of the CCDT is shown to have good blue noise characteristics, comparable in quality to those of state-of-the-art methods, achieved at a fraction of the runtime. Our CCDT method may be applied also to an arbitrary density function to produce non-uniform point distributions. These may be used to half-tone grayscale images.     

Gift-wrapping based preimage computation algorithm

Based on a classical convex hull algorithm called gift-wrapping, the purpose of the paper is to provide a new algorithm for computing the vertices of a polytope called preimage—roughly the set of naive digital planes containing a finite subset S of Z³. The vertices of the upper hemisphere, the ones of the lower hemisphere and at last the equatorial vertices are computed independently. The principle of the algorithm is based on duality and especially on the fact that the vertices of the preimage correspond to faces of the input set S or of its chords set S?S∪{(0,0,1)}. It allows to go from one vertex to another by gift-wrapping until the whole region of interest has been explored.     

Constrained delaunay triangulations

Given a set ofn vertices in the plane together with a set of noncrossing, straight-line edges, theconstrained Delaunay triangulation (CDT) is the triangulation of the vertices with the following properties: (1) the prespecified edges are included in the triangulation, and (2) it is as close as possible to the Delaunay triangulation. We show that the CDT can be built in optimalO(n logn) time using a divide-and-conquer technique. This matches the time required to build an arbitrary (unconstrained) Delaunay triangulation and the time required to build an arbitrary constrained (non-Delaunay) triagulation. CDTs, because of their relationship with Delaunay triangulations, have a number of properties that make them useful for the finite-element method. Applications also include motion planning in the presence of polygonal obstacles and constrained Euclidean minimum spanning trees, spanning trees subject to the restriction that some edges are prespecified.     

Composite Geometric Concepts and Polynomial Predictability

We study the predictability of geometric concepts, in particular those defined by boolean combinations of simple geometric objects. First, we give a negative results, showing that the problem of predicting the class of convex polytopes encoded by listing their vertices is prediction complete for P. Thus, an efficient solution to this prediction problem implies the existence of efficient solutions to all prediction problems whose associated evaluation problems are in P. Assuming the existence of a one-way function that is hard on iterates, there are such prediction problems which do not admit efficient solutions. Thus we show under minimal cryptographic assumptions that the class of convex polytopes encoded by listing their vertices is not predictable. As a side effect, we show that determining membership in the convex hull of a given set of points is complete for P with respect to log space reductions. Next, we establish the predictability of the class consisting of unions of a fixed number of flats by reducing its prediction problem to that of the class of flats, which has previously been shown to be predictable. Finally, we give an Occam algorithm for predicting fixed finite unions of boxes. Both constructive results for flats and boxes hold if the dimension is variable.     

A linear time algorithm for max-min length triangulation of a convex polygon

We consider the following planar max-min length triangulation problem: given a set of n points in the Euclidean plane, find a triangulation such that the length of the shortest edge in the triangulation is maximized. In this paper, a linear time algorithm is proposed for computing the max-min length triangulation of a set of points in convex position. In addition, an O(nlogn) time algorithm is proposed for computing the max-min length k-set triangulation of a set of points in convex position, where we are to compute a set of k vertices such that the max-min length triangulation on them is minimized over all possible k-set. We further show that the graph version of max-min length triangulation is NP-complete, and some common heuristics such as greedy algorithm are in general not able to give a bounded-ratio approximation to the max-min length triangulation.     

On the pseudoboundary of unstable polytopes of polynomials

The pseudoboundary of a polytope is defined to be the set of all polynomials in the polytope each of which has at least one zero on the imaginary axis. It is proven that a “section” of the pseudoboundary corresponding to any frequency “ω₀” is itself a polytope whose vertices lie in the exposed two-dimensional faces of the given polytope. A simple algorithm is proposed to generate all the vertex polynomials of any section of the pseudoboundary of a polytope. An illustrative example is given     

Polytope-based computation of polynomial ranges

Polynomial ranges are commonly used for numerically solving polynomial systems with interval Newton solvers. Often ranges are computed using the convex hull property of the tensorial Bernstein basis, which is exponential size in the number n of variables. In this paper, we consider methods to compute tight bounds for polynomials in n variables by solving two linear programming problems over a polytope. We formulate a polytope defined as the convex hull of the coefficients with respect to the tensorial Bernstein basis, and we formulate several polytopes based on the Bernstein polynomials of the domain. These Bernstein polytopes can be defined by a polynomial number of halfspaces. We give the number of vertices, the number of hyperfaces, and the volume of each polytope for n=1,2,3,4, and we compare the computed range widths for random n-variate polynomials for n?10. The Bernstein polytope of polynomial size gives only marginally worse range bounds compared to the range bounds obtained with the tensorial Bernstein basis of exponential size.     

<Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>-Optimal Nonparametric Frontier Estimation via Linear Programming

A frontier estimation method for a set of points on a plane is proposed, being optimal in L₁-norm on a given class of β-Holder boundary functions under β ∈ (0, 1]. The estimator is defined as sufficiently regular linear combination of kernel functions centered in the sample points, which covers all these points and whose associated support is of minimal surface. The linear combination weights are calculated via solution of the related linear programming problem. The L₁-norm of the estimation error is demonstrated to be convergent to zero with probability one, with the optimal rate of convergence.     

A Tight Lower Bound for Computing the Diameter of a 3D Convex Polytope

The diameter of a set P of n points in ℝ ^d is the maximum Euclidean distance between any two points in P. If P is the vertex set of a 3-dimensional convex polytope, and if the combinatorial structure of this polytope is given, we prove that, in the worst case, deciding whether the diameter of P is smaller than 1 requires Ω(nlog n) time in the algebraic computation tree model. It shows that the O(nlog n) time algorithm of Ramos for computing the diameter of a point set in ℝ³ is optimal for computing the diameter of a 3-polytope. We also give a linear time reduction from Hopcroft’s problem of finding an incidence between points and lines in ℝ² to the diameter problem for a point set in ℝ⁷.     

Generating well-shaped d-dimensional Delaunay Meshes

A d-dimensional simplicial mesh is a Delaunay triangulation if the circumsphere of each of its simplices does not contain any vertices inside. A mesh is well shaped if the maximum aspect ratio of all its simplices is bounded from above by a constant. It is a long-term open problem to generate well-shaped d-dimensional Delaunay meshes for a given polyhedral domain. In this paper, we present a refinement-based method that generates well-shaped d-dimensional Delaunay meshes for any PLC domain with no small input angles. Furthermore, we show that the generated well-shaped mesh has O(n) d-simplices, where n is the smallest number of d-simplices of any almost-good meshes for the same domain. Here a mesh is almost-good if each of its simplices has a bounded circumradius to the shortest edge length ratio.     

Minimal roughness property of the Delaunay triangulation

A set of scattered data in the plane consists of function values measured on a set of data points in R². A surface model of this set may be obtained by triangulating the set of data points and constructing the Piecewise Linear Interpolating Surface (PLIS) to the given function values. The PLIS is combined of planar triangular facets with vertices at the data points. The roughness measure of a PLIS is the L² norm squared of the gradient of the piecewise linear surface, integrated over the triangulated region and obviously depends on the specific triangulation. In this paper we prove that the Delaunay triangulation of the data points minimizes the roughness measure of a PLIS, for any fixed set of function values. This Theorem connects for the first time, as far as we know, the geometry of the Delaunay triangulation with the properties of the PLIS defined over it.     

On fractional faces of the metric polytope

The integrality recognition problem is considered on a sequence M _{n, k} of nested relaxations of a Boolean quadric polytope, including the rooted semimetric M _n and metric M _{n, 3} polytopes. The constraints of the metric polytope cut off all faces of the rooted semimetric polytope that contain only fractional vertices. This makes it possible to solve the integrality recognition problem on M _n in polynomial time. To solve the integrality recognition problem on the metric polytope, we consider the possibility of cutting off all fractional faces of M _{n, 3} by a certain relaxation M _{n, k} . The coordinates of points of the metric polytope are represented in homogeneous form as a three-dimensional block matrix. We show that in studying the question of cutting off the fractional faces of the metric polytope, it is sufficient to consider only constraints in the form of triangle inequalities.     

An algorithm for enumerating all vertices of a convex polyhedron

A bounded, convex polyhedronP inR ⁿ can be defined as the intersection of a finite number of halfspaces. Frequently, such polyhedronsP form the feasible regions of optimization problems; sometimes an optimum can only be determined when all vertices ofP are known. This paper describes an algorithm to enumerate these vertices with the help of graphs and a concept by Mañas and Nedoma [2]. Using this algorithm, it will be attempted to estimate the expected number of vertices of the examples employed by Liebling [1].     

Efficient minimum spanning tree construction without Delaunay triangulation

Given n points in a plane, a minimum spanning tree is a set of edges which connects all the points and has a minimum total length. A naive approach enumerates edges on all pairs of points and takes at least Ω(n2) time. More efficient approaches find a minimum spanning tree only among edges in the Delaunay triangulation of the points. However, Delaunay triangulation is not well defined in rectilinear distance. In this paper, we first establish a framework for minimum spanning tree construction which is based on a general concept of spanning graphs. A spanning graph is a natural definition and not necessarily a Delaunay triangulation. Based on this framework, we then design an O(nlogn) sweep-line algorithm to construct a rectilinear minimum spanning tree without using Delaunay triangulation.     

Computing the external geodesic diameter of a simple polygon

Given a simple polygonP ofn vertices, we present an algorithm that finds the pair of points on the boundary ofP that maximizes theexternal shortest path between them. This path is defined as theexternal geodesic diameter ofP. The algorithm takes0(n ²) time and requires0(n) space. Surprisingly, this problem is quite different from that of computing theinternal geodesic diameter ofP. While the internal diameter is determined by a pair of vertices ofP, this is not the case for the external diameter. Finally, we show how this algorithm can be extended to solve theall external geodesic furthest neighbours problem.     

The 2-facility centdian network problem

The p-facility centdian network problem consists of finding the p points that minimize a convex combination of the p-center and p-median objective functions. The vertices and local centers constitute a dominating set for the 1-facility centdian; i.e., it contains an optimal solution for all instances of the problem. Hooker et al. (1991) give a theoretical result to extend the dominating sets for the 1-facility problems to the corresponding p-facility problems. They claim that the set of vertices and local centers is also a dominating set for the p-facility centdian problem. We give a counterexample and an alternative finite dominating set for p=2. We propose a solution procedure for a network that improves the complexity of the exhaustive search in the dominating set. We also provide a very efficient algorithm that solves the 2-centdian on a tree network with complexity O(n²).     

Filtering Relocations on a Delaunay Triangulation

Updating a Delaunay triangulation when its vertices move is a bottleneck in several domains of application. Rebuilding the whole triangulation from scratch is surprisingly a very viable option compared to relocating the vertices. This can be explained by several recent advances in efficient construction of Delaunay triangulations. However, when all points move with a small magnitude, or when only a fraction of the vertices move, rebuilding is no longer the best option. This paper considers the problem of efficiently updating a Delaunay triangulation when its vertices are moving under small perturbations. The main contribution is a set of filters based upon the concept of vertex tolerances. Experiments show that filtering relocations is faster than rebuilding the whole triangulation from scratch under certain conditions.     

线性控制系统多面体区域的生存性判别

利用非光滑分析, 讨论线性控制系统多面体区域的生存性判别. 对于有界多面体(利用有限点集的凸包来表示), 其生存性判别只需检验其在极点处是否满足生存性条件, 去掉了以往对输入集合为多面体的要求, 这种生存性判别方法简便易行. 最后利用所给出的生存性条件讨论了生存性设计.