Most man-made environments, such as urban and indoor scenes, consist of a setof parallel and orthogonal planar structures. These structures are approximatedby the Manhattan world assumption, in which notion can be represented as aManhattan frame (MF). Given a set of inputs such as surface normals orvanishing points, we pose an MF estimation problem as a consensus setmaximization that maximizes the number of inliers over the rotation searchspace. Conventionally, this problem can be solved by a branch-and-boundframework, which mathematically guarantees global optimality. However, thecomputational time of the conventional branch-and-bound algorithms is ratherfar from real-time. In this paper, we propose a novel bound computation methodon an efficient measurement domain for MF estimation, i.e., the extendedGaussian image (EGI). By relaxing the original problem, we can compute thebound with a constant complexity, while preserving global optimality.Furthermore, we quantitatively and qualitatively demonstrate the performance ofthe proposed method for various synthetic and real-world data. We also show theversatility of our approach through three different applications: extension tomultiple MF estimation, 3D rotation based video stabilization, and vanishingpoint estimation (line clustering).