Technical Report CS0596

Title: Maximal Sets of K-increasing Subseouences with Applications To Counting Points in Triangles
Authors: R. Bar-Yehuda and S. Fogel
Abstract: We consider the problem of finding a maximal set of disjoint increasing subsequences of length k of a given sequence of real numbers. We achieve an O(nlogn + mk^2) algorithm, where m is the number of sequences found. Our algorithm is of a geometric nature. Using this result we show how to partition a sequence of n real numbers into 2*lower_bound(sqrt(n)) monotone subsequences in time O(n^1.5), an improvement over the best previous algorithm. An application to a fundamental problem in computational geometry is shown. Given n points in the plane, pteprocess them into an O(n log n) data structure such that counting points inside a query triangle can be done in time O(sqrt(n)*logn). The best preprocessing algorithm for this problem runs in time O(n^1.5*logn). We improve this time to O(n^1.5). In fact, our algorithm permits a linear tradeoff between preprocessing and query time.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1989
To the main CS technical reports page

Computer science department, Technion