A Geometric Fitting Problem of Two Corresponding Sets of Points on a Line

Hiroshi IMAI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E74-A   No.4   pp.665-668
Publication Date: 1991/04/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Issue on Discrete Mathematics and Its Applications)

Full Text: PDF>>
Buy this Article

This paper gives an O(n log n)-time algorithm for the following problem: min Σni=1|xi-ai| s.t.x1x2xn 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.