Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
Data Structure
Randomized Algorithm
Subscribe
Academic
Publications
A Randomized Algorithm for Weighted Approximation of Points by a Step Function
A Randomized Algorithm for Weighted Approximation of Points by a Step Function,10.1007/9783642174582_25,JinYi Liu
Edit
A Randomized Algorithm for Weighted Approximation of Points by a Step Function
BibTex

RIS

RefWorks
Download
JinYi Liu
The problem considered in this paper is: given an integer k > 0 and a set P of n points in the plane each with a corresponding nonnegative weight, find a step function f with k steps that minimize the maximum weighted vertical distance between f and all the points in P. We present a
randomized algorithm
to solve the problem in O(nlogn) expected running time. The bound is obviously optimal for the unsorted input. The previously best known algorithm runs in O(nlog2 n) worstcase time. Another merit of the algorithm is its simplicity. The algorithm is just a randomized implementation of Frederickson and Johnson’s matrix searching technique, and it only exploits a simple data structure.
Conference:
Conference on Combinatorial Optimization and Applications  COCOA
, pp. 300308, 2010
DOI:
10.1007/9783642174582_25
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
(
adsabs.harvard.edu
)
More »
References
(14)
Linear Approximation of Simple Objects
(
Citations: 65
)
Kasturi R. Varadarajan
,
Pankaj K. Agarwal
Journal:
Information Processing Letters  IPL
, vol. 62, no. 2, pp. 8994, 1997
Approximating Points by a Piecewise Linear Function: I
(
Citations: 2
)
Danny Z. Chen
,
Haitao Wang
Conference:
International Symposium on Algorithms and Computation  ISAAC
, pp. 224233, 2009
Introduction to Algorithms, Second Edition
(
Citations: 12540
)
Thomas H. Cormen
,
Charles E. Leiserson
,
Ronald L. Rivest
,
Clifford Stein
Published in 2001.
Fitting rectilinear polygonal curves to a set of points in the plane
(
Citations: 10
)
José Miguel DíazBáñez
,
Juan A. Mesa
Journal:
European Journal of Operational Research  EJOR
, vol. 130, no. 1, pp. 214222, 2001
Fitting a Step Function to a Point Set
(
Citations: 4
)
Hervé Fournier
,
Antoine Vigneron
Conference:
European Symposium on Algorithms  ESA
, pp. 442453, 2008