A fundamental problem in computational geometry is to compute an obstacle-avoiding Euclidean shortest path between two points in the plane. The case of this problem on polygonal obstacles is well studied. In this paper, we consider the problem version on curved obstacles, commonly modeled as splinegons. A splinegon can be viewed as replacing each edge of a polygon by a convex curved edge (polygons are special splinegons). Each curved edge is assumed to be of O(1) complexity. Given in the plane two points s and t and a set of @math pairwise disjoint splinegons with a total of @math vertices, we compute a shortest s-to-t path avoiding the splinegons, in @math time, where k is a parameter sensitive to the structures of the input splinegons and is upper-bounded by @math . In particular, when all splinegons are convex, @math is proportional to the number of common tangents in the free space (called "free common tangents") among the splinegons. We develop techniques for solving the problem on the general (non-convex) splinegon domain, which also improve several previous results. In particular, our techniques produce an optimal output-sensitive algorithm for a basic visibility problem of computing all free common tangents among @math pairwise disjoint convex splinegons with a total of @math vertices. Our algorithm runs in @math time and @math space, where @math is the number of all free common tangents. Even for the special case where all splinegons are convex polygons, the previously best algorithm for this visibility problem takes @math time.
It is not clear how to apply the continuous Dijkstra approach @cite_26 @cite_9 to our problem (even when all splinegons are discs) due to the curved obstacle boundaries. For example, Mitchell's approach @cite_9 uses a data structure for processing wavelet dragging queries by modeling them as high-dimensional radical-free semialgebraic range queries. In , however, such queries would involve not only radical numbers but also inverse trigonometric operations (e.g., arcsine), and hence similar techniques do not seem to apply. Hershberger and Suri's approach @cite_26 relies heavily on a conforming subdivision defined by the vertices of the polygonal obstacles. In our problem, however, it seems highly elusive to determine a set of @math vertices or points that can help build such a subdivision. One might attempt to use the splinegon vertices to build such a subdivision. But, an important property used by the subdivision @cite_26 is that the generator of every wavelet must be one of the obstacle vertices. Yet in , a generator need not be a splinegon vertex.
@cite_9 @cite_26
2137312224 2079132777 2040904149 1997019093
Abstract This paper describes a novel method to construct solid rational T-splines for complex genus-zero geometry from boundary surface triangulations. We first build a parametric mapping between the triangulation and the boundary of the parametric domain, a unit cube. After that we adaptively subdivide the cube using an octree subdivision, project the boundary nodes onto the input triangle mesh, and at the same time relocate the interior nodes via mesh smoothing. This process continues until the surface approximation error is less than a pre-defined threshold. T-mesh is then obtained by pillowing the subdivision result one layer on the boundary and its quality is improved. Templates are implemented to handle extraordinary nodes and partial extraordinary nodes in order to get a gap-free T-mesh. The obtained solid T-spline is C 2 -continuous except for the local region around each extraordinary node and partial extraordinary node. The boundary surface of the solid T-spline is C 2 -continuous everywhere except for the local region around the eight nodes corresponding to the eight corners of the parametric cube. Finally, a Bezier extraction technique is used to facilitate T-spline based isogeometric analysis. The obtained Bezier mesh is analysis-suitable with no negative Jacobians. Several examples are presented in this paper to show the robustness of the algorithm. In this paper, we present an approach that automatically constructs a trivariate tensor-product B-spline solid via a gradient-based optimization approach. Given six boundary B-spline surfaces for a solid, this approach finds the internal control points so that the resulting trivariate B-spline solid is valid in the sense the minimal Jacobian of the solid is positive. It further minimizes a volumetric functional to improve resulting parametrization quality. For a trivariate B-spline solid even with moderate shape complexity, direct optimization of the Jacobian of the B-spline solid is computationally prohibitive since it would involve thousands of design variables and hundreds of thousands of constraints. We developed several techniques to address this challenge. First, we develop initialization methods that can rapidly generate initial parametrization that are valid or near-valid. We then use a divide-and-conquer approach to partition the large optimization problem into a set of separable sub-problems. For each sub-problem, we group the B-spline coefficients of the Jacobian determinant into different blocks and make one constraint for each block of coefficients. This is achieved by taking an aggregate function, the Kreisselmeier-Steinhauser function value of the elements in each block. With block aggregation, it reduces the dimension of the problem dramatically. In order to further reduce the computing time at each iteration, a hierarchical optimization approach is used where the input boundary surfaces are coarsened to difference levels. We optimize the distribution of internal control points for the coarse representation first, then use the result as initial parametrization for optimization at the next level. The resulting parametrization can then be further optimized to improve the mesh quality. Optimized trivariate parametrization from various boundary surfaces and the corresponding parametrization metric are given to illustrate the effectiveness of the approach. We extend the results of straight-edged computational geometry into the curved world by defining a pair of new geometric objects, thesplinegon and thesplinehedron, as curved generalizations of the polygon and polyhedron. We identify three distinct techniques for extending polygon algorithms to splinegons: the carrier polygon approach, the bounding polygon approach, and the direct approach. By these methods, large groups of algorithms for polygons can be extended as a class to encompass these new objects. In general, if the original polygon algorithm has time complexityO(f(n)), the comparable splinegon algorithm has time complexity at worstO(Kf(n)) whereK represents a constant number of calls to members of a set of primitive procedures on individual curved edges. These techniques also apply to splinehedra. In addition to presenting the general methods, we state and prove a series of specific theorems. Problem areas include convex hull computation, diameter computation, intersection detection and computation, kernel computation, monotonicity testing, and monotone decomposition, among others. In a companion paper (see Self-Similarity: Part I-Splines and Operators), we characterized the class of scale-invariant convolution operators: the generalized fractional derivatives of order gamma. We used these operators to specify regularization functionals for a series of Tikhonov-like least-squares data fitting problems and proved that the general solution is a fractional spline of twice the order. We investigated the deterministic properties of these smoothing splines and proposed a fast Fourier transform (FFT)-based implementation. Here, we present an alternative stochastic formulation to further justify these fractional spline estimators. As suggested by the title, the relevant processes are those that are statistically self-similar; that is, fractional Brownian motion (fBm) and its higher order extensions. To overcome the technical difficulties due to the nonstationary character of fBm, we adopt a distributional formulation due to Gel'fand. This allows us to rigorously specify an innovation model for these fractal processes, which rests on the property that they can be whitened by suitable fractional differentiation. Using the characteristic form of the fBm, we then derive the conditional probability density function (PDF) p(BH(t)|Y), where Y= BH(k)+n[k] kisinZ are the noisy samples of the fBm BH(t) with Hurst exponent H. We find that the conditional mean is a fractional spline of degree 2H, which proves that this class of functions is indeed optimal for the estimation of fractal-like processes. The result also yields the optimal [minimum mean-square error (MMSE)] parameters for the smoothing spline estimator, as well as the connection with kriging and Wiener filtering