TR#: | CS0596 |

Class: | CS |

Title: | Maximal Sets of K-increasing Subseouences with Applications To Counting Points in Triangles |

Authors: | R. Bar-Yehuda and S. Fogel |

CS0596.pdf | |

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. |

Copyright | The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1989/CS/CS0596), 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