We study the problem of computing the similarity between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in 3D-polyhedral terrains-can be transformed vertically by...
详细信息
ISBN:
(纸本)9781450300162
We study the problem of computing the similarity between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in 3D-polyhedral terrains-can be transformed vertically by a linear transformation of the third coordinate (scaling and translation). We present a randomized algorithm that minimizes the maximum vertical distance between the graphs of the two functions, over all linear transformations of one of the terrains, in O(n(4/3) polylog n) expected time, where n is the total number of vertices in the graphs of the two functions. We also study the computation of similarity between two univariate or bivariate functions by minimizing the area or volume between their graphs. For univariate functions we give a (1 + epsilon)-approximation algorithm for minimizing the area that runs in O(n/root epsilon) time, for any fixed epsilon > 0. The (1 + epsilon)-approximation algorithm for the bivariate version, where volume is minimized, runs in O(n/epsilon(2)) time, for any fixed epsilon > 0, provided the two functions are defined over the same triangulation of their domain.
The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. We describe an algorithm that constructs the Reeb graph of a Morse f...
详细信息
The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. We describe an algorithm that constructs the Reeb graph of a Morse function defined on a 3-manifold. Our algorithm maintains connected components of the two dimensional levels sets as a dynamic graph and constructs the Reeb graph in O(n log n + n log g(log log g)(3)) time, where n is the number of triangles in the tetrahedral mesh representing the 3-manifold and g is the maximum genus over all level sets of the function. We extend this algorithm to construct Reeb graphs of d-manifolds in O(n log n(log log n)(3)) time, where n is the number of triangles in the simplicial complex that represents the d-manifold. Our result is a significant improvement over the previously known O(n(2)) algorithm. Finally, we present experimental results of our implementation and demonstrate that our algorithm for 3-manifolds performs efficiently in practice. (C) 2008 Elsevier B.V. All rights reserved.
The optimal solution of a geometric program (GP) can be sensitive to variations in the problem data. Robust geometric programming can systematically alleviate the sensitivity problem by explicitly incorporating a mode...
详细信息
The optimal solution of a geometric program (GP) can be sensitive to variations in the problem data. Robust geometric programming can systematically alleviate the sensitivity problem by explicitly incorporating a model of data uncertainty in a GP and optimizing for the worst-case scenario under this model. However, it is not known whether a general robust GP can be reformulated as a tractable optimization problem that interior-point or other algorithms can efficiently solve. In this paper we propose an approximation method that seeks a compromise between solution accuracy and computational efficiency. The method is based on approximating the robust GP as a robust linear program (LP), by replacing each nonlinear constraint function with a piecewise-linear (PWL) convex approximation. With a polyhedral or ellipsoidal description of the uncertain data, the resulting robust LP can be formulated as a standard convex optimization problem that interior-point methods can solve. The drawback of this basic method is that the number of terms in the PWL approximations required to obtain an acceptable approximation error can be very large. To overcome the "curse of dimensionality" that arises in directly approximating the nonlinear constraint functions in the original robust GP, we form a conservative approximation of the original robust GP, which contains only bivariate constraint functions. We show how to find globally optimal PWL approximations of these bivariate constraint functions.
In this paper, a multiple piecewise-linear function is constructed for generating multi-scroll chaotic attractors from the sixth-order Chua system. This approach has been verified both in theoretical analysis and comp...
详细信息
ISBN:
(纸本)9780769534947
In this paper, a multiple piecewise-linear function is constructed for generating multi-scroll chaotic attractors from the sixth-order Chua system. This approach has been verified both in theoretical analysis and computer simulations.
Reflexes have been viewed as integrated motions with the centrally generated motors commands to produce adaptive movement. In this paper, a walking pattern generator for humanoid robots based on piecewiselinear funct...
详细信息
ISBN:
(纸本)9781424406012
Reflexes have been viewed as integrated motions with the centrally generated motors commands to produce adaptive movement. In this paper, a walking pattern generator for humanoid robots based on piecewiselinearfunctions and inspired by passive walking is considered. To deal with lateral and frontal disturbances, sensory feedback is realized based on the inverse pendulum model. The reflex system that highly adapts and controls the movement of the humanoid robot, when a large disturbance occurs, is combined with the motion pattern generator and proposed in a unified form with regards to three types of sudden events. Experiments using Fujitsu's humanoid robot HOAP-3 demonstrate that a reflex movement is successfully integrated with the rhythmic motion when there are sudden changes in floor level, when obstacles suddenly appear, and in the presence of a large disturbance. The proposed reflex system therefore contributes toward the safe interaction of humanoid robots with the environment.
Emerging 3-D displays show several views of the scene simultaneously. A direct transmission of a selection of these views is impractical., because various types of displays support a different number of views and the ...
详细信息
ISBN:
(纸本)0819460958
Emerging 3-D displays show several views of the scene simultaneously. A direct transmission of a selection of these views is impractical., because various types of displays support a different number of views and the decoder has to interpolate the intermediate views. The transmission of multiview image information can be simplified by only transmitting the texture data for the central view and a corresponding depth map. Additional to the coding of the texture data, this technique requires the efficient coding of depth maps. Since the depth map represents the scene geometry and thereby covers the 3-D perception of the scene. sharp edges corresponding to object boundaries, should be preserved. We propose an algorithm that models depth maps using pieceivise-linearfunctions (platelets). To adapt to varying scene detail, we employ a quadtree decomposition that divides the image into blocks of variable size, each block being approximated by one platelet. In order to preserve sharp object boundaries, the support area of each platelet is adapted to the object boundary. The subdivision of the quadtree and the selection of the platelet type are optimized such that a global rate-distortion trade-off is realized. Experimental results show that the described method can improve the resulting picture quality after compression of depth maps by 1 - 3 dB when compared to a JPEG-2000 encoder.
The paper deals with a flow distribution problem with a piecewise-linear cost function. The problem is formulated as a piecewise-linear programming problem which is not separable with respect to separate variable grou...
详细信息
The paper deals with a flow distribution problem with a piecewise-linear cost function. The problem is formulated as a piecewise-linear programming problem which is not separable with respect to separate variable group. The method for solving this problem is based on the extension of the idea of the simplex method to the class of non-separable piecewise-linear problems. It secures finding of a local solution to the problem after a finite number of iterations. The method uses the peculiarities of the problem constraints that make it possible to decompose the matrix of constraints to smaller ones and thus to diminish the volume of calculations.
In this paper, a new application of the Hough transform is developed using fundamental ideas of the randomized Hough transform. The method detects and predicts piecewise-linear signals from serial samples with noise.
In this paper, a new application of the Hough transform is developed using fundamental ideas of the randomized Hough transform. The method detects and predicts piecewise-linear signals from serial samples with noise.
The generalized order linear complementarity problem (in the setting of a finite dimensional vector lattice) is the problem of finding a solution to the piecewise-linear system x AND (M1x + q1 ) AND (M2x + q2) AND ......
详细信息
The generalized order linear complementarity problem (in the setting of a finite dimensional vector lattice) is the problem of finding a solution to the piecewise-linear system x AND (M1x + q1 ) AND (M2x + q2) AND ... AND (M(k)x + q(k)) = 0, where M(i)'s are linear transformations and q(i)'s are vectors. This problem is equivalent to the generalized linear complementarity problem considered by Cottle and Dantzig [J. Combin. Theory, 8 (1970), pp- 79-90.]. Using degree theory, a comprehensive analysis of existence, uniqueness, and stability aspects of this problem is presented.
暂无评论