Counting inversions, offline orthogonal range counting, and related problems

Timothy M. Chan, Mihai Pǎtraşcu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We give an O(n√lg n)-time algorithm for counting the number of inversions in a permutation on n elements. This improves a long-standing previous bound of O(n lg n/ lg lg n) that followed from Dietz's data structure [WADS'89], and answers a question of Andersson and Petersson [SODA'95]. As Dietz's result is known to be optimal for the related dynamic rank problem, our result demonstrates a significant improvement in the offline setting. Our new technique is quite simple: we perform a "vertical partitioning" of a trie (akin to van Emde Boas trees), and use ideas from external memory. However, the technique finds numerous applications: for example, we obtain • in d dimensions, an algorithm to answer n offline orthogonal range counting queries in time O(n lgd-2+1/dn); • an improved construction time for online data structures for orthogonal range counting; • an improved update time for the partial sums problem; • faster Word RAM algorithms for finding the maximum depth in an arrangement of axis-aligned rectangles, and for the slope selection problem. As a bonus, we also give a simple (1 + ε)-approximation algorithm for counting inversions that runs in linear time, improving the previous O(n lg lg n) bound by Andersson and Petersson.

Original languageEnglish (US)
Title of host publicationProceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms
Pages161-173
Number of pages13
StatePublished - May 6 2010
Externally publishedYes
Event21st Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, United States
Duration: Jan 17 2010Jan 19 2010

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other21st Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityAustin, TX
Period1/17/101/19/10

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Counting inversions, offline orthogonal range counting, and related problems'. Together they form a unique fingerprint.

  • Cite this

    Chan, T. M., & Pǎtraşcu, M. (2010). Counting inversions, offline orthogonal range counting, and related problems. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 161-173). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).