http://swrc.ontoware.org/ontology#Article
A Geometric Fitting Problem of Two Corresponding Sets of Points on a Line
en
IMAI Hiroshi
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
E74-A
4
665-668
1991-04-25
copyright©1991 IEICE
Institute of Electronics, Information and Communication Engineers
https://search.ieice.org/