Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeometric and Combinatorial Properties of Well-Centered Triangulations in Three and Higher Dimensions
122
0
0.0
(
0
)
Added by
Evan VanderZee
Publication date
2009
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
An n-simplex is said to be n-well-centered if its circumcenter lies in its interior. We introduce several other geometric conditions and an algebraic condition that can be used to determine whether a simplex is n-well-centered. These conditions, together with some other observations, are used to describe restrictions on the local combinatorial structure of simplicial meshes in which every simplex is well-centered. In particular, it is shown that in a 3-well-centered (2-well-centered) tetrahedral mesh there are at least 7 (9) edges incident to each interior vertex, and these bounds are sharp. Moreover, it is shown that, in stark contrast to the 2-dimensional analog, where there are exactly two vertex links that prevent a well-centered triangle mesh in R^2, there are infinitely many vertex links that prohibit a well-centered tetrahedral mesh in R^3.
rate research
Read More
Meshes composed of well-centered simplices have nice orthogonal dual meshes (the dual Voronoi diagram). This is useful for certain numerical algorithms that prefer such primal-dual mesh pairs. We prove that well-centered meshes also have optimality properties and relationships to Delaunay and minmax angle triangulations. We present an iterative algorithm that seeks to transform a given triangulation in two or three dimensions into a well-centered one by minimizing a cost function and moving the interior vertices while keeping the mesh connectivity and boundary vertices fixed. The cost function is a direct result of a new characterization of well-centeredness in arbitrary dimensions that we present. Ours is the first optimization-based heuristic for well-centeredness, and the first one that applies in both two and three dimensions. We show the results of applying our algorithm to small and large two-dimensional meshes, some with a complex boundary, and obtain a well-centered tetrahedralization of the cube. We also show numerical evidence that our algorithm preserves gradation and that it improves the maximum and minimum angles of acute triangulations created by the best known previous method.
A completely well-centered tetrahedral mesh is a triangulation of a three dimensional domain in which every tetrahedron and every triangle contains its circumcenter in its interior. Such meshes have applications in scientific computing and other fields. We show how to triangulate simple domains using completely well-centered tetrahedra. The domains we consider here are space, infinite slab, infinite rectangular prism, cube and regular tetrahedron. We also demonstrate single tetrahedra with various combinations of the properties of dihedral acuteness, 2-well-centeredness and 3-well-centeredness.
The one-round discrete Voronoi game, with respect to a $n$-point user set $U$, consists of two players Player 1 ($mathcal{P}_1$) and Player 2 ($mathcal{P}_2$). At first, $mathcal{P}_1$ chooses a set of facilities $F_1$ following which $mathcal{P}_2$ chooses another set of facilities $F_2$, disjoint from $F_1$. The payoff of $mathcal{P}_2$ is defined as the cardinality of the set of points in $U$ which are closer to a facility in $F_2$ than to every facility in $F_1$, and the payoff of $mathcal{P}_1$ is the difference between the number of users in $U$ and the payoff of $mathcal{P}_2$. The objective of both the players in the game is to maximize their respective payoffs. In this paper we study the one-round discrete Voronoi game where $mathcal{P}_1$ places $k$ facilities and $mathcal{P}_2$ places one facility and we have denoted this game as $VG(k,1)$. Although the optimal solution of this game can be found in polynomial time, the polynomial has a very high degree. In this paper, we focus on achieving approximate solutions to $VG(k,1)$ with significantly better running times. We provide a constant-factor approximate solution to the optimal strategy of $mathcal{P}_1$ in $VG(k,1)$ by establishing a connection between $VG(k,1)$ and weak $epsilon$-nets. To the best of our knowledge, this is the first time that Voronoi games are studied from the point of view of $epsilon$-nets.
We present a simple algorithm for computing higher-order Delaunay mosaics that works in Euclidean spaces of any finite dimensions. The algorithm selects the vertices of the order-$k$ mosaic from incrementally constructed lower-order mosaics and uses an algorithm for weighted first-order Delaunay mosaics as a black-box to construct the order-$k$ mosaic from its vertices. Beyond this black-box, the algorithm uses only combinatorial operations, thus facilitating easy implementation. We extend this algorithm to compute higher-order $alpha$-shapes and provide open-source implementations. We present experimental results for properties of higher-order Delaunay mosaics of random point sets.
In this paper I present several novel, efficient, algorithmic techniques for solving some multidimensional geometric data management and analysis problems. The techniques are based on several data structures from computational geometry (e.g. segment tree and range tree) and on the well-known sweep-line method.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
