Abstract
Given a planar setS ofn points,maxdominance problems consist of computing, for everyp εS, some function of the maxima of the subset ofS that is dominated byp. A number of geometric and graph-theoretic problems can be formulated as maxdominance problems, including the problem of computing a minimum independent dominating set in a permutation graph, the related problem of finding the shortest maximal increasing subsequence, the problem of enumerating restricted empty rectangles, and the related problem of computing the largest empty rectangle. We give an algorithm for optimally solving a class of maxdominance problems. A straightforward application of our algorithm yields improved time bounds for the above-mentioned problems. The techniques used in the algorithm are of independent interest, and include a linear-time tree computation that is likely to arise in other contexts.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. J. Atallah and G. N. Frederickson, A Note on Finding a Maximum Empty Rectangle,Discrete Applied Mathematics, Vol. 13, No. 1, pp. 87–91 (1986).
A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974.
M. J. Atallah, G. K. Manacher, and J. Urrutia, Finding a Minimum Independent Dominating Set in a Permutation Graph, Purdue C.S. Tech. Rept.
A. Aggarwal and S. Suri, Fast Algorithms for Computing the Largest Empty Rectangle,Proc. 3rd ACM Symposium on Computational Geomtry, June 1987 (to appear).
B. Bhattacharya and H. ElGindy, Fast Algorithms for the Maximum Empty Rectangle Problem, University of Pennsylvania and Simon Fraser University Tech. Repts., March 1987.
B. Chazelle, Computing on a Free Tree via Complexity-Preserving Mappings,Proc. 25th Annual IEEE Symposium on Foundations of Computer Science, pp. 358–368, 1984.
B. Chazelle, R. L. Drysdale, and D. T. Lee, Computing the Largest Empty Rectangle,SIAM Journal on Computing, Vol. 15, No. 1, pp. 300–315 (1986).
E. W. Dijkstra, Some Beautiful Arguments Using Mathematical Induction,Acta Informatica, Vol. 13, No. 1, pp. 1–8 (1980).
R. B. K. Dewar, S. M. Merritt, and M. Sharir, Some Modified Algorithms for Dijkstra's Longest Upsequence Problem,Acta Informatica, Vol. 18, No. 1, pp. 1–15 (1982).
M. Farber and J. M. Keil, Domination in Permutation Graphs,Journal of Algorithms, 6, pp. 309–321 (1985).
A. Naamad, D. T. Lee, and W.-L. Hsu, On the Maximum Empty Rectangle Problem,Discrete Applied Mathematics, Vol. 8, pp. 267–277 (1984).
M. Orlowski, A New Algorithm for the Largest Empty Rectangle Problem, manuscript.
M. H. Overmars and J. Van Leeuwen, Maintenance of Configurations in the Plane,Journal of Computer and Systems Sciences, Vol. 23, pp. 166–204 (1981).
T. H. K. Prasad and C. P. Rangan, An Improved Algorithm for the Maximum Empty Rectangle Problem, IIT Madras Tech. Rept., March 1987.
Author information
Authors and Affiliations
Additional information
Communicated by D. T. Lee.
The research of this author was supported by the Office of Naval Research under Grants N00014-84-K-0502 and N00014-86-K-0689, and the National Science Foundation under Grant DCR-8451393, with matching funds from AT&T.
This author's research was supported by the National Science Foundation under Grant DCR-8506361.
Rights and permissions
About this article
Cite this article
Atallah, M.J., Kosaraju, S.R. An efficient algorithm for maxdominance, with applications. Algorithmica 4, 221–236 (1989). https://doi.org/10.1007/BF01553888
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01553888