|
Imagine thinking about the 2-dimensional plane, and drawing a triangle whose extreme points are (0,1), (3,2) and (-1,3). How many integer-valued points lie inside this triangle? For this example, there are eight points inside the triangle in total: the original three extreme points and five internal points, (0,1), (0,2), (1,1), (1,2) and (2,2). You can check this by drawing the triangle on the grid of a maths copybook.In general we can consider the same question in any number of dimensions - we could consider the problem for a tetrahedron in 3-dimensions, but also for many more dimensions, and for non-regular shapes. The only thing that we really insist on is that the shape we consider should have straight edges and flat faces, and that the shape must be closed off (otherwise we would have to deal with infinitely many points). These shapes are called Polytopes , and can be described by a system of equations in many dimensions. The integer-valued points are also called Lattice points .This research project is concerned with the computational problem of counting lattice points in polytopes. What this means is that we would like to write a computer algorithm (a program) that would take a description of a polytope in many dimensions and output the number of lattice points that polytope contains. We are also interested in a related problem called Sampling - given a description of a polytope, can we write a computer algorithm to choose a Random lattice point from the entire set of lattice points? The best way of thinking about this is to think about someone tossing a coin, and then making a decision based on that: for Sampling, an algorithm will have to toss coins at many stages in order to guarantee that the Lattice point that gets output is random enough.Unfortunately, it is very difficult to come up with efficient algorithms to either count or to sample lattice points. This is because counting lattice points is an example of a sharp P -complete problem, and these are notoriously difficult for computers to solve efficiently. If we have as much time as we like, then there is no difficulty, but even at the stage of 5 or 6 dimensions, the time taken by an exact algorithm can spiral out of control. For this reason, the goal of this project is to come up with algorithms to approximately count (get a good estimate ) and approximately sample these points. The possibilities for this are much better. We plan to focus on this goal for certain classes of polytopes which have important applications in statistics. One application that requires lattice point Sampling is the area of statistical disclosure control , where we have a statistical table of numbers, and we make statistics from that table. In the case of sensitive data (for example, tables constructed from hospital records), it isvery important that the statistics will not reveal the values (or likely values) of any table entries. This motivates the sampling of statistical tables (to compare typical tables with the true table).
|