About Me

I am passionate about Science, Education and Environmental Protection. For my PhD, I study Computational Geometry and Topology with broader interests in Theoretical Computer Science.

Selected Projects

A Constrained Resampling Strategy for Mesh Improvement
with A. Hassen, A. Rushdi, S. Mitchell, J. Owens, M. Ebeida SGP'17
Abstract In many geometry processing applications, it is required to improve an initial mesh in terms of multiple quality objectives. Despite the availability of several mesh generation algorithms with provable guarantees, such generated meshes may only satisfy a subset of the objectives. The conflicting nature of such objectives makes it challenging to establish similar guarantees for each combination, e.g., angle bounds and vertex count. In this paper, we describe a versatile strategy for mesh improvement by interpreting quality objectives as spatial constraints on resampling and develop a toolbox of local operators to improve the mesh while preserving desirable properties. Our strategy judiciously combines smoothing and transformation techniques allowing increased flexibility to practically achieve multiple objectives simultaneously. We apply our strategy to both planar and surface meshes demonstrating how to simplify Delaunay meshes while preserving element quality, eliminate all obtuse angles in a complex mesh, and maximize the shortest edge length in a Voronoi tessellation far better than the state-of-the-art. | PDF
Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm
with C. Bajaj, M. Ebeida, A. Mahmoud, S. Mitchell, J. Owens and A. Rushdi SoCG'18
Abstract We study the problem of decomposing a volume bounded by a smooth surface into a collection of Voronoi cells. Unlike the dual problem of conforming Delaunay meshing, a principled solution to this problem for generic smooth surfaces remained elusive. VoroCrust leverages ideas from & alpha;-shapes and the power crust algorithm to produce unweighted Voronoi cells conforming to the surface, yielding the first provably-correct algorithm for this problem. Given an & epsilon;-sample on the bounding surface, with a weak & sigma;-sparsity condition, we work with the balls of radius & delta; times the local feature size centered at each sample. The corners of this union of balls are the Voronoi sites, on both sides of the surface. The facets common to cells on opposite sides reconstruct the surface. For appropriate values of & epsilon;, & sigma; and & delta;, we prove that the surface reconstruction is isotopic to the bounding surface. With the surface protected, the enclosed volume can be further decomposed into an isotopic volume mesh of fat Voronoi cells by generating a bounded number of sites in its interior. Compared to state-of-the-art methods based on clipping, VoroCrust cells are full Voronoi cells, with convexity and fatness guarantees. Compared to the power crust algorithm, VoroCrust cells are not filtered, are unweighted, and offer greater flexibility in meshing the enclosed volume by either structured grids or random samples. | arXiv
Economical Delone Sets for Approximating Convex Bodies
with D. Mount SWAT'18
Abstract Convex bodies are ubiquitous in computational geometry and optimization theory. The high combinatorial complexity of multidimensional convex polytopes has motivated the development of algorithms and data structures for approximate representations. This paper demonstrates an intriguing connection between convex approximation and the classical concept of Delone sets from the theory of metric spaces. It shows that with the help of a classical structure from convexity theory, called a Macbeath region, it is possible to construct an epsilon-approximation of any convex body as the union of O(1/epsilon^{(d-1)/2}) ellipsoids, where the center points of these ellipsoids form a Delone set in the Hilbert metric associated with the convex body. Furthermore, a hierarchy of such approximations yields a data structure that answers epsilon-approximate polytope membership queries in O(\log (1/\epsilon)) time. This matches the best asymptotic results for this problem, by a data structure that both is simpler and arguably more elegant. | PDF