CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Discrete and Computational Geometry
Org: Binay Bhattacharya (Simon Fraser University)

BINAY BHATTACHARYA, Simon Fraser University
Application of computational geometry to network location problems  [PDF]

The main objective of this talk is to show that computational geometry tools can be effectively applied to solve network location problems. In particular we show that the {\em p-center} problem in general networks can be transformed to Klee's measure problem (KMP) in computational geometry. When the underlying network is a partial k-tree (k-fixed), we showed that the {\em p-center} problem can be efficiently solved by transforming the problem to a range search problem.

DAVID KIRKPATRICK, University of British Columbia
Polygonal paths of bounded curvature  [PDF]

We present an elementary and purely geometric proof of a characterization result, analogous to the classical result of Dubins, for minimum length {\em polygonal} paths satisfying a new sharpness-of-turn constraint. This provides a discrete analogue of continuous motion of bounded curvature, and also gives a fundamentally new proof of Dubins' original result as a limiting case of our constructions.

[Joint work with Valentin Polishchuk, University of Helsinki]

LADISLAV STACHO, Simon Fraser University
Problems on Geometric Graphs  [PDF]

Classical graph theory problems assume graphs are combinatorial structures given as incidence matrix. Many times these graphs represent communication networks which pose additional properties, for example, a geometric information about the location of vertices. We discuss how this information can help to reduce computational resources, in particular space/memory, and how these algorithms can become local in a sense that at any given time only local subgraph is available to the algorithm to compute next step.

CAOAN WANG, Memorial university of newfoundland
A note on Hamiltonian tetrahedralizations  [PDF]

'Hamiltonian tetrahedralization problem' asks whether or not every convex polyhedron can be partitioned into tetrahedra such that the dual graph has an Hamiltonian Path (HP). There exist some convex polyhedron which does not have any Hamiltonian tetrahedralization by pulling. Bistellar flips may transfer some of these cases to have a Hamiltonian tetrahedralization. O(n) flips may be required for a polyhedron with n vertices.

SUE WHITESIDES, University of Victoria BC
Approaches to Hard (and Potentially Deep and Wet) Problems in Computational Geometry  [PDF]

Path planning gives rise to NPhard problems in geometry, as do placement problems in wireless sensor networks. Theoretical methods for dealing with hardness include approximation, probabilistic, and FPT approaches. We review some results, then describe an approach that combines probabilistic methods, simulation, and experimentation to modify the initial geometry problem, with success defined experimentally. We describe this process in the context of path planning and device placement for eventual underwater environmental monitoring applications.

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria