Motion video analysis using planar parallax
Harpreet S. Sawhney
IS&T/SPIE Electronic Imaging 1994
Let (X, <) be a partially ordered set. A linear extension x1, x2, ... has a bump whenever xi<xi+1, and it has a jump whenever xiand xi+1are incomparable. The problem of finding a linear erxtension that minimizes the number of jumps has been studied extensively; Pulleyblank shows that it is NP-complete in the general case. Fishburn and Gehrlein raise the question of finding a linear extension that minimizes the number of bumps. We show that the bump number problem is closely related to the well-studied problem of scheduling unit-time tasks with a precedence partial order on two identical processors. We point out that a variant of Gabow's linear-time algorithm for the two-processor scheduling problem solves the bump number problem. Habib, Möhring, and Steiner have independently discovered a different polynomial-time algorithm to solve the bump number problem. © 1988 Kluwer Academic Publishers.
Harpreet S. Sawhney
IS&T/SPIE Electronic Imaging 1994
F. Odeh, I. Tadjbakhsh
Archive for Rational Mechanics and Analysis
W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
Yi Zhou, Parikshit Ram, et al.
ICLR 2023