Problems in Discrete and Computational Geometry

点击翻译按钮获取中文摘要

My research area is discrete and computational geometry. In discrete geometry we investigate properties of geometric objects with the objective of using these properties to design efficient algorithms in the field of computational geometry. Computational geometry is a branch of computer science devoted to the study of algorithms and data structures for geometric problems. The input of a computational geometry problem consists of geometric objects (such as points, lines, circles, etc.) that come from application domains such as wireless networks, computer graphics, and robotics. An algorithm that is proven to be theoretically efficient often fails to be practically useful as it may be too complex to understand and implement or it may only become efficient when the size of the input is unreasonably large. The main goal of my ongoing research is to seek a greater understanding of different geometric structures to design simple algorithms for geometric problems. I provide a sample of the type of problems that I will concentrate on. Technology used in daily life strongly relies on networks. For instance, one can think of the network of cellphone antennas in Canada. Since antennas have physical locations, this network can be modeled as a geometric graph where antennas are represented by points with connections/edges between any two antennas within each other's transmission range. Designing networks possessing various properties has a rich background. A required property for the cellphone network is that any two antennas should be able to exchange messages, and thus the network must be connected. This introduces the problem of computing a shortest connected network. Another problem is to replace omnidirectional antennas in wireless networks with directional antennas while maintaining network connectivity. Directional antennas are desirable in many ways, for example, they require lower transmission power and cause less interference. I will study these types of problems on geometric networks. Many structures studied in discrete and computational geometry have a requirement of being non-crossing, i.e., their edges do not cross each other. This is particularly true for sub-structures of complete geometric graphs that involve a minimization criteria, for example, the shortest connected network and shortest connected path. However, when the underlying graph is not complete or when we deal with a maximization criteria the non-crossing property is not guaranteed. Crossings can cause errors, for example, interference between antennas, collision between moving objects, or inconsistencies in the layout of a VLSI circuit. I will focus on computing non-crossing structures in these circumstances. A main framework that I exploit to solve geometric problems is to first extract various geometric and combinatorial properties involved in the input, and then combine these properties with suitable data structures to design efficient algorithms/solutions for the problem.