Computing infeasibility certificates for combinatorial problems through Hilbert’s Nullstellensatz

Systems of polynomial equations with coefficients over a field K can be used to concisely model combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over the algebraic closure of the field K. In this paper, we investigate an algorithm aimed at proving combinatorial infeasibility based on the observed low degree of Hilbert’s Nullstellensatz certificates for polynomial systems arising in combinatorics, and based on fast large-scale linear-algebra computations over K. We also describe several mathematical ideas for optimizing our algorithm, such as using alternative forms of the Nullstellensatz for computation, adding carefully constructed polynomials to our system, branching and exploiting symmetry. We report on experiments based on the problem of proving the non-3-colorability of graphs. We successfully solved graph instances with almost two thousand nodes and tens of thousands of edges.     

Region-expansion for the Voronoi diagram of 3D spheres

Given a set of spheres in 3D, constructing its Voronoi diagram in Euclidean distance metric is not easy at all even though many mathematical properties of its structure are known. This Voronoi diagram has been known for many important applications from science and engineering. In this paper, we characterize the Voronoi diagram of spheres in three-dimensional Euclidean space, which is also known as an additively weighted Voronoi diagram, and propose an algorithm to construct the diagram. Starting with the ordinary Voronoi diagram of the centers of the spheres, the proposed region-expansion algorithm constructs the desired diagram by expanding the Voronoi region of each sphere, one after another. We also show that the whole Voronoi diagram of n spheres can be constructed in O(n³) time in the worst case.     

AnO(n logn) plane-sweep algorithm forL 1 andL ∞ Delaunay triangulations

TheDelaunay diagram on a set of points in the plane, calledsites, is the straight-line dual graph of the Voronoi diagram. When no degeneracies are present, the Delaunay diagram is a triangulation of the sites, called theDelaunay triangulation. When degeneracies are present, edges must be added to the Delaunay diagram to obtain a Delaunay triangulation. In this paper we describe an optimalO(n logn) plane-sweep algorithm for computing a Delaunay triangulation on a possibly degenerate set of sites in the plane under theL ₁ metric or theL _∞ metric.     

Quasi-triangulation and interworld data structure in three dimensions

It is well-known that the Voronoi diagram of points and the power diagram for weighted points, such as spheres, are cell complexes, and their respective dual structures, i.e. the Delaunay triangulation and the regular triangulation, are simplicial complexes. Hence, the topologies of these diagrams are usually stored in their dual complexes using a very compact data structure of arrays.The topology of the Voronoi diagram of three-dimensional spheres in the Euclidean distance metric, on the other hand, is stored in a radial edge data structure which is not as compact as the data structure used for the Voronoi diagram of points and the power diagram for weighted points.In this paper, we define a dual structure of the Voronoi diagram of three-dimensional spheres called a quasi-triangulation and present its important properties. Based on the properties of a quasi-triangulation, we propose a data structure, called an interworld data structure, based on arrays to compactly store the topology of the quasi-triangulation with a guaranteed query performance.     

三维点集Voronoi图的算法实现

对现有三维点集Voronoi图的生成算法进行深入研究,提出并实现由Delaunay三角剖分构建Voronoi图的算法．首先采用随机增量局部转换计算Delaunay三角剖分,然后再根据对偶特性构建Voronoi图．该算法健壮性很高,适用于处理各种非完全共面三维点集．     

一种基于逐点插入Delaunay三角剖分生成Voronoi图的算法

采用改进的逐点插入算法生成Voronoi图。该算法在逐点插入的过程中生成凸壳,进而生成Delaunay三角剖分。在生成Voronoi图的实现过程中,通过遍历三角形的边顶点快速识别相关的三角形组,进而生成Voronoi图。试验结果表明,该算法能实现,成功生成Voronoi图。     

基于Voronoi 最小邻近点集的Delaunay 三角化方法

针对局部条件下网格生成的需求,提出一种基于节点的Delaunay 三角化 生成算法,该算法以Delaunay 三角形及其对偶Voronoi 图的局部性特征为基础,通过在局部 搜索最小Voronoi 邻近点集,来生成约束点附近的局部网格,通过建立背景索引网格,来提 高算法效率。给出算法的原理证明、程序实现、效率分析和测试结果,并给出了算法的应用 领域。     

基于Delaunay三角剖分生成Voronoi图算法

针对Delaunay三角网生长算法和间接生成Voronoi图算法构网效率不高的问题,提出了一种Delaunay三角网生长法间接生成Voronoi图的改进算法。该算法以点集凸壳上一边快速生成种子三角形,定义了半封闭边界点的概念,在三角形扩展过程中动态删除封闭点及半封闭边界点,加快Delaunay三角网生成速度。然后又定义了有序目标三角形的概念,该算法能迅速查找点的有序目标三角形,生成无射线的Voronoi图;考虑凸壳上点的特性,借助三个无穷点生成带射线的Voronoi图。通过实验结果分析表明,改进的算法执行效率有了很大提高。     

多尺度形态滤波及弹性匹配技术在类星体谱线识别中的应用

本文提出了一种类星体谱线证认方法。首先针对特征为极值点的信号，研究了多尺度膨胀（腐蚀）关于极值点数的两种重要特性及其应用。其一是单调率特性，根据它自动选择滤波器尺度，有效地滤除脉冲噪声；另一种是单调性，它是＂从粗到精＂策略来重新恢复极值特征位置的理论基础。根据这些性质，对光谱进行多尺度膨胀（腐蚀）和特征恢复，以滤除脉冲噪声而不影响谱线特征。然后研究弹性匹配技术应用于谱线证认，并指出了匹配方法中参量的物理意义。该方法对其他一些应用领域也行之有效     

基于Voronoi图及其对偶图的反最近邻查询

最近邻查询是地理信息系统领域经常遇到的问题,而反最近邻查询是在最近邻查询的基础上提出的一种新的查询类型。在分析利用Voronoi图进行最近邻查询的基础上,提出了基于Voronoi图及其对偶图Delaunay图的反最近邻查询,大大缩小了在海量空间数据库中进行反最近邻查询的查询范围。     

Computability of Partial Delaunay Triangulation and Voronoi Diagram [Extended Abstract]

Using the domain-theoretic model for geometric computation, we define the partial Delaunay triangulation and the partial Voronoi diagram of N partial points in R² and show that these operations are domain-theoretically computable and effectively computable with respect to Hausdorff distance and Lebesgue measure. These results are obtained by showing that the map which sends three partial points to the partial disc passing through them is computable. This framework supports the design of robust algorithms for computing the Delaunay triangulation and the Voronoi diagram with imprecise input.     

Optimal partitioning for multi-vehicle systems using quadratic performance criteria

We consider the problem of characterizing a generalized Voronoi diagram that is relevant to a special class of area assignment problems for multi-vehicle systems. It is assumed that the motion of each vehicle is described by a second order mechanical system with time-varying linear or affine dynamics. The proposed generalized Voronoi diagram encodes information regarding the proximity relations between the vehicles and arbitrary target points in the plane. These proximity relations are induced by an anisotropic (generalized) distance function that incorporates the vehicle dynamics. In particular, the generalized distance is taken to be the minimum control effort required for the transition of a vehicle to an arbitrary target point with a small terminal speed at a fixed final time. The space we wish to partition corresponds to the union of all the terminal positions that can be attained by each vehicle using finite control effort. Consequently, the partition space has lower dimension than the state space of each vehicle. We show that, in the general case, the solution to the proposed partitioning problem can be associated with a power Voronoi diagram generated by a set of spheres in a five-dimensional Euclidean space for the computation of which efficient techniques exist in the relevant literature.     

A Real Polynomial Decision Algorithm Using Arbitrary-Precision Floating Point Arithmetic

We study the problem of deciding whether a system of real polynomial equations and inequalities has solutions, and if yes finding a sample solution. For polynomials with exact rational number coefficients the problem can be solved using a variant of the cylindrical algebraic decomposition (CAD) algorithm. We investigate how the CAD algorithm can be adapted to the situation when the coefficients are inexact, or, more precisely, Mathematica arbitrary-precision floating point numbers. We investigate what changes need to be made in algorithms used by CAD, and how reliable are the results we get.     

The Classical Theory of Invariants and Object Recognition Using Algebraic Curve and Surfaces

Combining implicit polynomials and algebraic invariants for representing and recognizing complicated objects proves to be a powerful technique. In this paper, we explore the findings of the classical theory of invariants for the calculation of algebraic invariants of implicit curves and surfaces, a theory largely disregarded in the computer vision community by a shadow of skepticism. Here, the symbolic method of the classical theory is described, and its results are extended and implemented as an algorithm for computing algebraic invariants of projective, affine, and Euclidean transformations. A list of some affine invariants of 4th degree implicit polynomials generated by the proposed algorithm is presented along with the corresponding symbolic representations, and their use in recognizing objects represented by implicit polynomials is illustrated through experiments. An affine invariant fitting algorithm is also proposed and the performance is studied.     

Euclidean Voronoi diagram of 3D balls and its computation via tracing edges

Despite its important applications in various disciplines in science and engineering, the Euclidean Voronoi diagram for spheres, also known as an additively weighted Voronoi diagram, in 3D space has not been studied as much as it deserves. In this paper, we present an algorithm to compute the Euclidean Voronoi diagram for 3D spheres with different radii. The presented algorithm follows Voronoi edges one by one until the construction is completed in O(mn) time in the worst-case, where m is the number of edges in the Voronoi diagram and n is the number of spherical balls. As building blocks, we show that Voronoi edges are conics that can be precisely represented as rational quadratic Bézier curves. We also discuss how to conveniently represent and process Voronoi faces which are hyperboloids of two sheets.     

The parametrized complexity of knot polynomials

We study the parametrized complexity of the knot (and link) polynomials known as Jones polynomials, Kauffman polynomials and HOMFLY polynomials. It is known that computing these polynomials is hard in general. We look for parameters of the combinatorial presentation of knots and links which make the computation of these polynomials to be fixed parameter tractable, i.e., in the complexity class FPT. If the link is explicitly presented as a closed braid, the number of its strands is known to be such a parameter. In a generalization thereof, if the link is explicitly presented as a combination of compositions and rotations of k-tangles the link is called k-algebraic, and its algebraicity k is such a parameter. The previously known proofs that, for this parameter, the link polynomials are in FPT uses the so called skein modules, and is algebraic in its nature. Furthermore, it is not clear how to find such an algebraic presentation from a given link diagram. We look at the treewidth of two combinatorial presentation of links: the crossing diagram and its shading diagram, a signed graph. We show that the treewidth of these two presentations and the algebraicity of links are all linearly related to each other. Furthermore, we characterize the k-algebraic links using the pathwidth of the crossing diagram. Using this, we can apply algorithms for testing fixed treewidth to find k-algebraic presentations in polynomial time. From this we can conclude that also treewidth and pathwidth are parameters of link diagrams for which the knot polynomials are FPT. For the Kauffman and Jones polynomials (but not for the HOMFLY polynomials) we get also a different proof for FPT via the corresponding result for signed Tutte polynomials.     

Verified Computation of Fast Decreasing Polynomials

In this paper the problem of verified numerical computation of algebraic fast decreasing polynomials approximating the Dirac delta function is considered. We find the smallest degree of the polynomials and give precise estimates for this degree. It is shown that the computer algebra system Maple does not always graph such polynomials reliably because of evaluating the expressions in usual floating-point arithmetic. We propose a procedure for verified computation of the polynomials and use it to produce their correct graphic presentation in Maple.     

Delaunay meshing of isosurfaces

We present an isosurface meshing algorithm, DelIso, based on the Delaunay refinement paradigm. This paradigm has been successfully applied to mesh a variety of domains with guarantees for topology, geometry, mesh gradedness, and triangle shape. A restricted Delaunay triangulation, dual of the intersection between the surface and the three-dimensional Voronoi diagram, is often the main ingredient in Delaunay refinement. Computing and storing three-dimensional Voronoi/Delaunay diagrams become bottlenecks for Delaunay refinement techniques since isosurface computations generally have large input datasets and output meshes. A highlight of our algorithm is that we find a simple way to recover the restricted Delaunay triangulation of the surface without computing the full 3D structure. We employ techniques for efficient ray tracing of isosurfaces to generate surface sample points, and demonstrate the effectiveness of our implementation using a variety of volume datasets.     

Three-dimensional beta shapes

The Voronoi diagram of a point set has been extensively used in various disciplines ever since it was first proposed. Its application realms have been even further extended to estimate the shape of point clouds when Edelsbrunner and Mücke introduced the concept of α-shape based on the Delaunay triangulation of a point set.In this paper, we present the theory of β-shape for a set of three-dimensional spheres as the generalization of the well-known α-shape for a set of points. The proposed β-shape fully accounts for the size differences among spheres and therefore it is more appropriate for the efficient and correct solution for applications in biological systems such as proteins.Once the Voronoi diagram of spheres is given, the corresponding β-shape can be efficiently constructed and various geometric computations on the sphere complex can be efficiently and correctly performed. It turns out that many important problems in biological systems such as proteins can be easily solved via the Voronoi diagram of atoms in proteins and β-shapes transformed from the Voronoi diagram.