Conference paper
Walking on an arrangement topologically
Tetsuo Asano, Leonidas J. Guibas, et al.
SCG 1991
In a paper in Journal of Algorithms13 (1992), 148-160, Hirschberg and Larmore introduced the traveler’s problem as a subroutine for constructing the B-tree. They gave an O(n5/3 log1/3n) time algorithm for solving the traveler’s problem of size n. In this paper, we improve their time bound to O(n3/2 log n). As a consequence, we build a B-tree in O(n3/2 log2n) time as compared to the O(n5/3 log4/3n) time algorithm of Hirschberg and Larmore. © 1995 Academic Press, Inc.
Tetsuo Asano, Leonidas J. Guibas, et al.
SCG 1991
Alok Aggarwal, Youngcheul Wee
Information Processing Letters
Lakshmi Ramachandran, Manika Kapoor, et al.
DIALM 2000
Alok Aggarwal, Maria Klawe
Discrete Applied Mathematics