Building footprints have been shown to be extremely useful in urban planning, infrastructure development, and roof modeling. Current methods for creating these footprints are often highly manual and rely largely on architectural blueprints or skilled modelers. In this work we will use aerial LIDAR data to generate building footprints automatically. Existing automatic methods have been mostly unsuccessful due to large amounts of noise around building edges. We present a novel Bayesian technique for automatically constructing building footprints from a pre-classified LIDAR point cloud. Our algorithm first computes a boundederror approximate building footprint using an application of the shortest path algorithm. We then determine the most probable building footprint by maximizing the posterior probability using linear optimization and simulated annealing techniques. We have applied our algorithm to more than 300 buildings in our data set and observe that we obtain accurate building footprints compared to the ground truth. Our algorithm is automatic and can be applied to other man-made shapes such as roads and telecommunication lines with minor modifications.