Linear Time Algorithm for Approximating a Curve by a Single-Peaked Curve

Given a function y = f(x) in one variable, we consider the problem of computing the single-peaked (unimodal) curve y =φ(x) minimizing the L₂-distance between them. If the input function f is a histogram with O(n) steps or a piecewise linear function with O(n) linear pieces, we design algorithms for computing φ in linear time. We also give an algorithm to approximate f with a function consisting of the minimum number of unimodal pieces under the condition that each unimodal piece is within a fixed L₂-distance from the corresponding portion of f.     

Approximating Gradients for Meshes and Point Clouds via Diffusion Metric

The gradient of a function defined on a manifold is perhaps one of the most important differential objects in data analysis. Most often in practice, the input function is available only at discrete points sampled from the underlying manifold, and the manifold is approximated by either a mesh or simply a point cloud. While many methods exist for computing gradients of a function defined over a mesh, computing and simplifying gradients and related quantities such as critical points, of a function from a point cloud is non-trivial.
In this paper, we initiate the investigation of computing gradients under a different metric on the manifold from the original natural metric induced from the ambient space. Specifically, we map the input manifold to the eigenspace spanned by its Laplacian eigenfunctions, and consider the so-called diffusion distance metric associated with it. We show the relation of gradient under this metric with that under the original metric. It turns out that once the Laplace operator is constructed, it is easier to approximate gradients in the eigenspace for discrete inputs (especially point clouds) and it is robust to noises in the input function and in the underlying manifold. More importantly, we can easily smooth the gradient field at different scales within this eigenspace framework. We demonstrate the use of our new eigen-gradients with two applications: approximating / simplifying the critical points of a function, and the Jacobi sets of two input functions (which describe the correlation between these two functions), from point clouds data.     

Approximating Points by a Piecewise Linear Function

Approximating points by piecewise linear functions is an intensively researched topic in computational geometry. In this paper, we study, based on the uniform error metric, an array of variations of this problem in 2-D and 3-D, including points with weights, approximation with violations, using step functions or more generally piecewise linear functions. We consider both the min-# (i.e., given an error tolerance ?, minimizing the size k of the approximating function) and min-? (i.e., given a size k of the approximating function, minimizing the error tolerance ?) versions of the problems. Our algorithms either improve on the previously best-known solutions or are the first known results for the respective problems. Our approaches are based on interesting geometric observations and algorithmic techniques. Some data structures we develop are of independent interest and may find other applications.     

Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem

Local search has been widely used in combinatorial optimization (Local Search in Combinatorial Optimization, Wiley, New York, 1997), however, in the case of multicriteria optimization almost no results are known concerning the ability of local search algorithms to generate “good” solutions with performance guarantee. In this paper, we introduce such an approach for the classical traveling salesman problem (TSP) problem (Proc. STOC’00, 2000, pp. 126–133). We show that it is possible to get in linear time, a -approximate Pareto curve using an original local search procedure based on the 2-opt neighborhood, for the bicriteria TSP(1,2) problem where every edge is associated to a couple of distances which are either 1 or 2 (Math. Oper. Res. 18 (1) (1993) 1).     

结合度量空间和时间的逻辑

与时态和空间有关的推理问题是人工智能研究中重要的组成部分,近年来时空逻辑的研究受到相关领域研究者的极大重视。以多维逻辑为框架表示时空知识,提出了一组将度量空间逻辑和时态逻辑相结合的逻辑模型PTL-MS、PTL-MS1、PTL-MS2,表示和推理随时间变化的距离关系,看成是时态逻辑和度量逻辑的迪卡尔乘积,给出了语义和语法,研究了它们的表达能力,用于时空约束满足问题、时空知识库以及移动对象数据库(MOD)等。     

基于局部线性逼近的流形学习算法

流形学习方法是根据流形的定义提出的一种非线性数据降维方法,主要思想是发现嵌入在高维数据空间的低维光滑流形.局部线性嵌入算法是应用比较广泛的一种流形学习方法,传统的局部线性嵌入算法的一个主要缺点就是在处理稀疏源数据时会失效,而实际应用中很多情况还要面对处理源数据稀疏的问题.在分析局部线性嵌入算法的基础上提出了基于局部线性逼近思想的流形学习算法,其通过采用直接估计梯度值的方法达到局部线性逼近的目的,从而实现高维非线性数据的维数约简,最后在S-曲线上进行稀疏采样测试取得良好降维效果.     

Linear Time Super-Helices

Thin elastic rods such as cables, phone coils, tree branches, or hair, are common objects in the real world but computing their dynamics accurately remains challenging. The recent Super-Helix model, based on the discrete equations of Kirchhoff for a piecewise helical rod, is one of the most promising models for simulating non-stretchable rods that can bend and twist. However, this model suffers from a quadratic complexity in the number of discrete elements, which, in the context of interactive applications, makes it limited to a few number of degrees of freedom - or equivalently to a low number of variations in curvature along the mean curve. This paper proposes a new, recursive scheme for the dynamics of a Super-Helix, inspired by the popular algorithm of Featherstone for serial multibody chains. Similarly to Featherstone's algorithm, we exploit the recursive kinematics of a Super-Helix to propagate elements inertias from the free end to the clamped end of the rod, while the dynamics is solved within a second pass traversing the rod in the reverse way. Besides the gain in linear complexity, which allows us to simulate a rod of complex shape much faster than the original approach, our algorithm makes it straightforward to simulate tree-like structures of Super-Helices, which turns out to be particularly useful for animating trees and plants realistically, under large displacements.     

Computing the Cover Array in Linear Time

Let x denote a given nonempty string of length n = |x| . A proper substring u of x is a proper cover of x if and only if every position of x lies within an occurrence of u within x . This paper introduces an array γ = γ[1..n] called the cover array in which each element γ[i] , 1 ≤ i ≤ n , is the length of the longest proper cover of x[1..i] or zero if no such cover exists. In fact it turns out that γ describes all the covers of every prefix of x . Several interesting properties of γ are established, and a simple algorithm is presented that computes γ on-line in Θ(n) time using Θ(n) additional space. Thus the new algorithm computes for all prefixes of x information that previous cover algorithms could compute only for x itself, and does so with no increase in space or time complexity.     

Computing the Cover Array in Linear Time

Abstract. Let x denote a given nonempty string of length n = |x| . A proper substring u of x is a proper cover of x if and only if every position of x lies within an occurrence of u within x . This paper introduces an array γ = γ[1..n] called the cover array in which each element γ[i] , 1 ≤ i ≤ n , is the length of the longest proper cover of x[1..i] or zero if no such cover exists. In fact it turns out that γ describes all the covers of every prefix of x . Several interesting properties of γ are established, and a simple algorithm is presented that computes γ on-line in Θ(n) time using Θ(n) additional space. Thus the new algorithm computes for all prefixes of x information that previous cover algorithms could compute only for x itself, and does so with no increase in space or time complexity.     

Online and Offline Algorithms for the Time-Dependent TSP with Time Zones

The time-dependent traveling salesman problem (TDTSP) is a variant of TSP with time-dependent edge costs. We study some restrictions of TDTSP where the number of edge cost changes are limited. We find competitive ratios for online versions of TDTSP. From these we derive polynomial time approximation algorithms for graphs with edge costs one and two. In addition, we present an approximation algorithm for the orienteering problem with edge costs one and two.     

Mathematical Morphology Based on Linear Combined Metric Spaces on Z2 (Part II): Constant Time Morphological Operations

Mathematical Morphology (MM) is a general method for image processing based on set theory. The two basic morphological operators are dilation and erosion. From these, several non linear filters have been developed, usually with polynomial complexity and this because the two basic operators depend strongly on the definition of the structural element. Most efforts to improve the algorithm's speed for each operator are based on structural element decomposition and/or efficient codification.In this second part, the concepts developed in part I (see Díaz de León and Sossa Azuela, Mathematical morphology based on linear combined metric spaces on Z¹ (part I): Fast distance transforms, Journal of Mathematical Imaging and Vision, Vol. 12, No. 2, pp. 137–154, 2000) are used to prove that it is possible to reduce the complexity of the morphological operators to zero complexity (constant time algorithms) for any regular discrete metric space and to eliminate the use of the structural element. In particular, this is done for an infinite family of metric spaces further defined. The use of the distance transformation is proposed for it comprises the information concerning all the discs included in a region to obtain fast morphological operators: erosions, dilations, openings and closings (of zero complexity) for an infinite (countable) family of regular metric spaces. New constant time, in contrast with the polynomial time algorithms, for the computation of these basics operators for any structural element are next derived by using this background. Practical examples showing the efficiency of the proposed algorithms, final comments and present research are also given here.     

Linear Time Logic Control of Discrete-Time Linear Systems

The control of complex systems poses new challenges that fall beyond the traditional methods of control theory. One of these challenges is given by the need to control, coordinate and synchronize the operation of several interacting submodules within a system. The desired objectives are no longer captured by usual control specifications such as stabilization or output regulation. Instead, we consider specifications given by linear temporal logic (LTL) formulas. We show that existence of controllers for discrete-time controllable linear systems and LTL specifications can be decided and that such controllers can be effectively computed. The closed-loop system is of hybrid nature, combining the original continuous dynamics with the automatically synthesized switching logic required to enforce the specification     

Approximating the crowd

The problem of “approximating the crowd” is that of estimating the crowd’s majority opinion by querying only a subset of it. Algorithms that approximate the crowd can intelligently stretch a limited budget for a crowdsourcing task. We present an algorithm, “CrowdSense,” that works in an online fashion where items come one at a time. CrowdSense dynamically samples subsets of the crowd based on an exploration/exploitation criterion. The algorithm produces a weighted combination of the subset’s votes that approximates the crowd’s opinion. We then introduce two variations of CrowdSense that make various distributional approximations to handle distinct crowd characteristics. In particular, the first algorithm makes a statistical independence approximation of the labelers for large crowds, whereas the second algorithm finds a lower bound on how often the current subcrowd agrees with the crowd’s majority vote. Our experiments on CrowdSense and several baselines demonstrate that we can reliably approximate the entire crowd’s vote by collecting opinions from a representative subset of the crowd.     

线性时间选择算法时间复杂度深入研究

算法研究是计算机科学的核心领域之一。文中针对元素选择问题及解此问题的线性时间选择算法进行了深入研究,详细分析并论证了期望情况下与最坏情况下线性时间选择算法的时间复杂度,并对拟中位数元素选择问题进行了深层次的拓展,通过计算比较求出了线性时间下的最小复杂度因子。以期有助于该算法在相关领域的应用。     

Splitting a Delaunay Triangulation in Linear Time

Abstract. Computing the Delaunay triangulation of n points requires usually a minimum of Ω(n log n) operations, but in some special cases where some additional knowledge is provided, faster algorithms can be designed. Given two sets of points, we prove that, if the Delaunay triangulation of all the points is known, the Delaunay triangulation of each set can be computed in randomized expected linear time.     

一种支持DTW距离的多元时间序列索引结构

现有的索引结构难以有效地支持DTW距离度量下的多元时间序列相似性搜索.首先给出一种将不等长多元时间序列转换为等长一元时间序列的方法,并证明这种转换满足下界距离引理;以此为基础,提出一种多元时间序列的DTW下界距离,并对其性质进行分析;然后,针对给出的下界距离,提出一种支持DTW距离度量的多元时间序列索引结构,对多元时间序列数据库进行有效组织;再给出多元时间序列相似模式搜索算法及流程,并证明该搜索方法具有非漏报性;最后,通过实验对所提方法的有效性进行验证.     

Solving the 2-Disjoint Paths Problem in Nearly Linear Time

Given four distinct vertices s₁,s₂,t₁, and t₂ of a graph G, the 2-disjoint paths problem is to determine two disjoint paths, p₁ from s₁ to t₁ and p₂ from s₂ to t₂, if such paths exist. Disjoint can mean vertex- or edge-disjoint. Both, the edge- and the vertex-disjoint version of the problem, are NP-hard in the case of directed graphs. For undirected graphs, we show that the O(mn)-time algorithm of Shiloach can be modified to solve the 2-vertex-disjoint paths problem in only O(n + mα(m,n)) time, where m is the number of edges in G, n is the number of vertices in G, and where α denotes the inverse of the Ackermann function. Our result also improves the running time for the 2-edge-disjoint paths problem on undirected graphs as well as the running times for the 2-vertex- and the 2-edge-disjoint paths problem on dags.