2020-08-06T07:41:57Zhttps://repository.dl.itc.u-tokyo.ac.jp/?action=repository_oaipmhoai:repository.dl.itc.u-tokyo.ac.jp:000489522020-04-17T06:40:58Z00009:00010:0001500034:00095:00096
A Geometric Fitting Problem of Two Corresponding Sets of Points on a Lineenghttp://hdl.handle.net/2261/00074077Journal ArticleIMAI, HiroshiThis 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 SciencesE74-A46656681991-04-25copyright©1991 IEICEpublisherhttps://repository.dl.itc.u-tokyo.ac.jp/?action=repository_action_common_download&item_id=48952&item_no=1&attribute_id=19&file_no=1Institute of Electronics, Information and Communication Engineershttps://search.ieice.org/2017-12-15