This paper aims at improving the accuracy and computational efficiency in reconstructing building boundaries from airborne Lidar points. We proposed an adaptive convex hull algorithm, which is a modified version of local convex hull algorithm in three ways. The candidate points for boundary are first selected to improve efficiency depending on their local density. Second, a searching-space is adjusted adaptively, based on raw data structure, to extract boundary points more robustly. Third, distance between two points and their IDs are utilized in detecting the seed points of inner boundary to distinguish between inner yards and inner holes due to errors or occlusions. The practicability of the approach were evaluated on two urban areas where various buildings exist. The proposed method showed less shape-dissimilarity(8.5%) and proved to be two times more efficient than the other method.