Research‎ > ‎

Geometry

I have always been a fan of art, design and geometry. The beauty of different geometric shapes has always attracted me. While growing up, I learned the inseparable relationship between mathematics and geometry and it made me more interested in this. I have always wondered how different geometric shapes vary from one to another just by their formulating equations. Thus I loved graphics, visualization, animation and all sorts of things relating to geometry. No wonder why I chose Computational Geometry as my undergraduate research topic. I was lucky enough to get Prof. Masud Hasan as my supervisor who is a great mentor and has variety of experiences in research in Computational Geometry. During my senior days, I tried to make a strong base of theoretical computer science specially in geometry. I approached some optimization problems of computational geometry and could devise efficient solutions for those. I still work on geometric optimizations and get immense pleasure in it.

Here is a list of my works on Computational Geometry:



1. Cutting a Convex Polyhedron out of a Sphere:  [pdf]
( in JCCGG '09, WALCOM '10 and Graphs and Combinatorics [accepted with mild correction])



Given a convex polyhedron P of n vertices inside a sphere Q, we give an O(n^3)-time algorithm that cuts P out of Q by using guillotine cuts and has cutting cost O((log n)^2) times the optimal.

This is the first algorithm for cutting a 3D geometric shape from another 3D geometric shape.






















2. Vindictive Voronoi Diagrams and Stabbing Delaunay Circles:
[pdf]
(in International Symposium on Voronoi Diagrams (ISVD), 2010, Canada)


In this paper we consider the following problem: Given a set of n Player1 sites in the plane and their Delaunay triangulation D, place minimum possible Player2 sites such that in the resulting Delaunay triangulation D' of the sites of both Players, the neighborship between Player1 sites are as less as possible. We first consider placing minimum number of Player2 sites such that no two Player1 sites are neighbors in D'. We show that to isolate a Player1 site p, two Player2 sites are both necessary and sufficient if p is in the convex hull of D, otherwise three Player2 sites are both necessary and sufficient. This gives a liner time algorithm to individually isolate all Player1 sites by 3n−h Player2 sites, where h is the number of sites in the convex hull of D. Then we give two more algorithms for this problem. The next algorithm runs also in linear time and uses 3(n−1)−h Player2 sites, but is much simpler. Our next algorithm uses 5|M| sites, where |M| is the size of a maximum matching in D, and runs in O( p root(nm)) time, where m is the number of edges of D. Then we consider isolating sites by components, where a component in D' is a maximal connected subset of sites of the same player. We show that it is possible to place n Player2 sites such that in D0 the number of components among Player1 sites is higher than that among Player2 sites. The above problems are related to at least two existing well known research topics: Voronoi games, where the strategy of each of the two players is to place sites such that in the resulting Voronoi diagram some certain criteria is optimized for each player, and proximity graphs, where this problem is known as minimum stabbing set of Delaunay circles. Our bound of 5|M| for the first problem would work better than known bound for the minimum stabbing set of Delaunay circles if M has a smaller size.


3. Cutting a Cornered Convex Polygon out of a Circle:
[pdf]
( in ICCIT '09 and Journal of Computers (JCP) )


The problem of cutting a convex polygon P out of a piece of planar material Q with minimum total cutting length is a well studied problem in computational  geometry. Researchers studied several variations of the problem, such as P and Q are convex or non-convex polygons and the cuts are line cuts or ray cuts. In this paper we consider yet another variation of the problem where Q is a circle and P is a convex polygon such that P is bounded by a half circle of Q and all the cuts are line cuts. We give two algorithms for solving this problem. Our first algorithm is an O(log n)-approximation algorithm with O(n) running time, where n is the number of edges of P. The second algorithm is a constant factor approximation algorithm with approximation ratio 6.48 and running time O(n^3).








3. Searching for the Centers of Spheres and Ellipsoids: [pdf]
(in ACT '09, India)




Biedl et al. first posed the problem of finding the center of a circle, starting from a point on the boundary and using a limited number of operations. They presented an open problem for searching the center of an ellipse in their paper. Later, Burr et al. solved that problem. However, in both of their works, they considered the searching space to be two dimensional. As a result their strategies do well on a plane. But in reality the searching space is three dimensional in most of the cases. In those cases we need an efficient strategy to find out the center of a sphere or in some cases, the center of an ellipsoid. In this paper, we have approached the problems of searching the center of a sphere and an ellipsoid. We have proposed here four different strategies for finding the center of a sphere. We have also proposed the strategy of searching the center of an ellipsoid.


Comments