Department of Computer Science, University of Tokyo
抄録
This paper gives an O(n log n)-time algorithm for the following problem: min Σni=1|xi-ai| s.t.x1≦x2≦...≦xn where ai(i=1, ..., n) are given constants and xi(i=1, ..., n) are variables. There has been given an O(n2)-time incremental algorithm, and we improve it by using the heap as a data structure and modify the incremental algorithm partly. This problem is a kind of the geometric fitting problem between two corresponding sets of points on a line which is related to some VLSI layout design problem.
内容記述
Special Section PAPER (Special Issue on Discrete Mathematics and Its Applications)
雑誌名
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
A Geometric Fitting Problem of Two Corresponding Sets of Points on a Line
A Geometric Fitting Problem of Two Corresponding Sets of Points on a Line 1991.pdf
(294.79KB)
