Search

The antiprism triangulation provides a natural way to subdivide a simplicial complex Δ , similar to barycentric subdivision, which appeared independently in combinatorial algebraic topology and computer science. It can be defined as the simplicial complex of chains of multi-pointed faces of Δ , from a combinatorial point of view, and by successively applying the antiprism construction, or balanced stellar subdivisions, on the faces of Δ , from a geometric point of view. This paper studies enumerative invariants associated to this triangulation, such as the transformation of the h-vector of Δ under antiprism triangulation, and algebraic properties of its Stanley–Reisner ring. Among other results, it is shown that the h-polynomial of the antiprism triangulation of a simplex is real-rooted and that the antiprism triangulation of Δ has the almost strong Lefschetz property over R for every shellable complex Δ . Several related open problems are discussed. [ABSTRACT FROM AUTHOR]

CGALmesh is the mesh generation software package of the Computational Geometry Algorithm Library (CGAL). It generates isotropic simplicial meshes—surface triangular meshes or volume tetrahedral meshes—from input surfaces, 3D domains, and 3D multidomains, with or without sharp features. The underlying meshing algorithm relies on restricted Delaunay triangulations to approximate domains and surfaces and on Delaunay refinement to ensure both approximation accuracy and mesh quality. CGALmesh provides guarantees on approximation quality and on the size and shape of the mesh elements. It provides four optional mesh optimization algorithms to further improve the mesh quality. A distinctive property of CGALmesh is its high flexibility with respect to the input domain representation. Such a flexibility is achieved through a careful software design, gathering into a single abstract concept, denoted by the oracle, all required interface features between the meshing engine and the input domain. We already provide oracles for domains defined by polyhedral and implicit surfaces. [ABSTRACT FROM AUTHOR]

Several sampling criteria had been proposed for C 2 smooth surfaces such that the reconstructed meshes from point samples are homeomorphic to the original surfaces. In this paper, based on a widely used sample criterion, we present proofs that give the upper and lower bounds of mesh quality (in terms of several triangle aspect ratios) for the reconstructed mesh. To make the proposed theoretical bounds useful in practical applications with real-world point data, we propose a novel mesh reconstruction method that works in three steps: (1) approximate Delaunay mesh reconstruction; (2) point data upsampling and (3) hole filling. Finally, examples are presented, which illustrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

We study the problem of visibility in polyhedral terrains in the presence of multiple viewpoints. We consider a triangulated terrain with m > 1 viewpoints (or guards) located on the terrain surface. A point on the terrain is considered visible if it has an unobstructed line of sight to at least one viewpoint. We study several natural and fundamental visibility structures: (1) the visibility map, which is a partition of the terrain into visible and invisible regions; (2) the colored visibility map, which is a partition of the terrain into regions whose points have exactly the same visible viewpoints; and (3) the Voronoi visibility map, which is a partition of the terrain into regions whose points have the same closest visible viewpoint. We study the complexity of each structure for both 1.5D and 2.5D terrains, and provide efficient algorithms to construct them. Our algorithm for the visibility map in 2.5D terrains improves on the only existing algorithm in this setting. To the best of our knowledge, the other structures have not been studied before. [ABSTRACT FROM AUTHOR]

A novel parallelization of the Lepp-bisection algorithm for triangulation refinement on multicore systems is presented. Randomization and wise use of the memory hierarchy are shown to highly improve algorithm performance. Given a list of selected triangles to be refined, random selection of candidates together with pre-fetching of Lepp-submeshes lead to a scalable and efficient multi-core parallel implementation. The quality of the refinement is shown to be preserved. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents a novel approach to handle large amounts of geometric data. A data stream clustering is used to reduce the amount of data and build a hierarchy of clusters. The data stream concept allows for the processing of very large data sets. The cluster hierarchy is then used in a dynamic triangulation to create a multiresolution model. It allows for the interactive selection of a different level of detail in various parts of the data. A method for removal multiple points from Delaunay triangulation is proposed. It is significantly faster than the traditional approach. The clustering and the triangulation are supplemented by an elliptical metric to handle data with anisotropic properties. Compared to the closest competitive method by Isenburg et al., the presented algorithm requires only a single pass over the data and offers a high flexibility. These advantages culminate in a long running time. The method was tested on several large digital elevation maps. The clustering phase can take up to a few hours. Once the cluster hierarchy is built, the terrains can be efficiently manipulated in real time. [Copyright &y& Elsevier]

Abstract: This paper discusses optimization of quality measures over first order Delaunay triangulations. Unlike most previous work, our measures relate to edge-adjacent or vertex-adjacent triangles instead of only to single triangles. We give efficient algorithms to optimize certain measures, including measures related to the area ratio of adjacent triangles, angle between outward normals of adjacent triangles (for polyhedral terrains), and number of convex vertices. Some other measures are shown to be NP-hard. These include maximum vertex degree, number of convex edges, and number of mixed vertices. For the latter two measures we provide, for any constant , factor approximation algorithms that run in and time (when the Delaunay triangulation is given). For minimizing the maximum vertex degree, the NP-hardness proof provides an inapproximability result. Our results are presented for the class of first order Delaunay triangulations, but also apply to triangulations where for every triangle at least two edges are fixed. The approximation result on maximizing the number of convex edges is also extended to k-th order Delaunay triangulations. [Copyright &y& Elsevier]

Abstract: We study the complexity and the i/o-efficient computation of flow on triangulated terrains. We present an acyclic graph, the descent graph, that enables us to trace flow paths in triangulations i/o-efficiently. We use the descent graph to obtain i/o-efficient algorithms for computing river networks and watershed-area maps in i/o''s, where r is the complexity of the river network and d of the descent graph. Furthermore we describe a data structure based on the subdivision of the terrain induced by the edges of the triangulation and paths of steepest ascent and descent from its vertices. This data structure can be used to report the boundary of the watershed of a query point q or the flow path from q in i/o''s, where s is the complexity of the subdivision underlying the data structure, is the number of i/o''s used for planar point location in this subdivision, and k is the size of the reported output. On α-fat terrains, that is, triangulated terrains where the minimum angle of any triangle is bounded from below by α, we show that the worst-case complexity of the descent graph and of any path of steepest descent is , where n is the number of triangles in the terrain. The worst-case complexity of the river network and the above-mentioned data structure on such terrains is . When α is a positive constant this improves the corresponding bounds for arbitrary terrains by a linear factor. We prove that similar bounds cannot be proven for Delaunay triangulations: these can have river networks of complexity . [Copyright &y& Elsevier]

Abstract: To reconstruct an object surface from a set of surface points, a fast, practical, and efficient priority driven algorithm is presented. The key idea of the method is to consider the shape changes of an object at the boundary of the mesh growing area and to create a priority queue to the advancing front of the mesh area according to the changes. The mesh growing process is then driven by the priority queue for efficient surface reconstruction. New and practical triangulation criteria are also developed to support the priority driven strategy and to construct a new triangle at each step of mesh growing in real time. The quality and correctness of the created triangles will be guaranteed by the triangulation criteria and topological operations. The algorithm can reconstruct an object surface from unorganized surface points in a fast and reliable manner. Moreover, it can successfully construct the surface of the objects with complex geometry or topology. The efficiency and robustness of the proposed algorithm is validated by extensive experiments. [Copyright &y& Elsevier]

Abstract: For a given convex polygon with inner angle no less than and boundary edge bounded by for , where is a given standard bar’s length, we investigate the problem of triangulating the polygon using some Steiner points such that (i) the length of each edge in triangulation is bounded by , where is a given constant and meets , and (ii) the number of non-standard bars in the triangulation is minimum. This problem is motivated by practical applications and has not been studied previously. In this paper, we present a heuristic to solve the above problem, which is based on the heuristic to generate a triangular mesh with less number of non-standard bars and shorter maximal edge length, and a process to make the length of each edge lower bounded. Our procedure is simple and easily implemented for this problem, and we prove that it has good performance guaranteed. [Copyright &y& Elsevier]

We consider four problems on distance estimation and object location which share the common flavor of capturing global information via informative node labels: low-stretch routing schemes [48], distance labeling [25], searchable small worlds [31], and triangulation-based distance estimation [34]. Focusing on metrics of low doubling dimension, we approach these problems with a common technique called rings of neighbors, which refers to a sparse distributed data structure that underlies all our constructions. Apart from improving the previously known bounds for these problems, our contributions include extending Kleinberg’s small world model to doubling metrics, and a short proof of the main result in Chan et al. [15]. Doubling dimension is a notion of dimensionality for general metrics that has recently become a useful algorithmic concept in the theoretical computer science literature. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

We show how to construct a stable hierarchical basis for piecewise quadratic C1 continuous splines defined on Powell–Sabin triangulations. We prove that this hierarchical basis is well suited for compressing surfaces. Our compression method does not require the construction of wavelets which are usually expensive to compute, but instead we use a stable quasi-interpolation scheme that achieves optimal approximation order. Numerical experiments demonstrate the high compression rate of the algorithm. [ABSTRACT FROM AUTHOR]

We consider point location in Delaunay triangulations with the aid of simple data structures. In particular, we analyze methods in which a simple data structure is used to first locate a point close to the query point. For points uniformly distributed on the unit square, we show that the expected point location complexities are Θ(√ of n ) for the Green–Sibson rectilinear search, Θ(n1/3) for Jump and Walk, Θ(n1/4) for BinSearch and Walk (which uses a 1-dimensional search tree), Θ(n0.056…) for search based on a random 2-d tree, and Θ(logn) for search aided by a 2-d median tree. [Copyright &y& Elsevier]

This paper presents a new fast method for polygonization of implicit surfaces. Our method put emphasis on the shape of triangles generated and on the polygonization speed. The main advantages of the triangulation presented are simplicity and the stable features that can be used for future expansion. The implementation is not complicated and only the standard data structures are used. This algorithm is based on the surface tracking scheme and it is compared with the well-known marching cubes algorithm that is based on the similar principle. The presented algorithm is accelerated by the space subdivision which is an effective technique to speed-up any geometric of this type. [Copyright &y& Elsevier]

We design a kinetic data structure for detecting collisions between two simple polygons in motion. In order to do so, we create a planar subdivision of the free space between the two polygons, called the external relative geodesic triangulation, which certifies their disjointness. We show how this subdivision can be maintained as a kinetic data structure when the polygons are moving, and analyze its performance in the kinetic setting. [Copyright &y& Elsevier]

This paper describes a new type of low-cost interactive active range finder and illustrates the effect of introducing interactivity to the range-acquisition process. The new range finder consists of only one camera and a laser pointer to which three LEDs are attached. When a user scans the laser, the camera captures the image of spots (one from the laser and the others from LEDs), and triangulation is carried out using the camera's viewing direction and the optical axis of the laser. The user interaction allows the range finder to acquire range data in which the sampling rate varies across the object depending on the underlying surface structures. Moreover, the processes of separating objects from the background and/or finding parts in the object can be achieved using the operator's knowledge of the objects. [ABSTRACT FROM AUTHOR]

The user experience (UX) is an emerging field in user research and design, and the development of UX evaluation methods presents a challenge for both researchers and practitioners. Different UX evaluation methods have been developed to extract accurate UX data. Among UX evaluation methods, the mixed-method approach of triangulation has gained importance. It provides more accurate and precise information about the user while interacting with the product. However, this approach requires skilled UX researchers and developers to integrate multiple devices, synchronize them, analyze the data, and ultimately produce an informed decision. In this paper, a method and system for measuring the overall UX over time using a triangulation method are proposed. The proposed platform incorporates observational and physiological measurements in addition to traditional ones. The platform reduces the subjective bias and validates the user’s perceptions, which are measured by different sensors through objectification of the subjective nature of the user in the UX assessment. The platform additionally offers plug-and-play support for different devices and powerful analytics for obtaining insight on the UX in terms of multiple participants. [ABSTRACT FROM AUTHOR]