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 Publications

The Inapproximability of Illuminating Polygons by α-Floodlights
A. Saeed, K. Harras, A. Mohamed CCCG'15
Abstract We consider variants of the art gallery problem where guard visibility is limited to a certain angular aperture α. We show that the problem is NP-hard even when guards can be located in the interior of the polygon. We then proceed to prove that both this problem and its vertex variant, where guard placement is restricted to the vertices of the polygon, are APX-hard. We observe that earlier constructions for such results in art gallery problems with 360° guards, usually required them to cover few specific elements. We exploit this by carefully updating the construction to replace 360° guards with α-floodlights. Similar transformations may be applicable to other constructions in traditional art gallery theorems, which is of independent interest. | PDF
2048 Without New Tiles Is Still Hard
A. Acharya, P. Dasler FUN'16
Abstract We study the computational complexity of a variant of the popular 2048 game in which no new tiles are generated after each move. As usual, instances are defined on rectangular boards of arbitrary size. We consider the natural decision problems of achieving a given constant tile value, score or number of moves. We also consider approximating the maximum achievable value for these three objectives. We prove all these problems are NP-hard by a reduction from 3SAT. Furthermore, we consider potential extensions of these results to a similar variant of the Threes! game. To this end, we report on a peculiar motion pattern, that is not possible in 2048, which we found much harder to control by similar board designs. | PDF | Play!
A Constrained Resampling Strategy for Mesh Improvement
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