×

zbMATH — the first resource for mathematics

On the heaviest increasing or decreasing subsequence of a permutation, and paths and matchings on weighted point sets. (English) Zbl 1374.05011
Márquez, Alberto (ed.) et al., Computational geometry. XIV Spanish meeting on computational geometry, EGC 2011, dedicated to Ferran Hurtado on the occasion of his 60th birthday, Alcalá de Henares, Spain, June 27–30, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-34190-8/pbk). Lecture Notes in Computer Science 7579, 175-184 (2012).
Summary: Let \(S = \{s(1), \dots, s(n)\}\) be a permutation of the integers \(\{1,\dots, n\}\). A subsequence of \(S\) with elements \(\{s(i _{1}), \dots, s(i _{k })\}\) is called an increasing subsequence if \(s(i _{1}) < \cdots < s(i _{k})\); It is called a decreasing subsequence if \(s(i _{1}) > \cdots > s(i_{k})\). The weight of a subsequence of \(S\), is the sum of its elements. In this paper, we prove that any permutation of \(\{1, \dots, n\}\) contains an increasing or a decreasing subsequence of weight greater than \(n\sqrt{2n/3}\).
Our motivation to study the previous problem arises from the following problem: Let \(P\) be a set of \(n\) points on the plane in general position, labeled with the integers \(\{1,\dots ,n\}\) in such a way that the labels of different points are different. A non-crossing path \(\Pi\) with vertices in \(P\) is an increasing path if when we travel along it, starting at one of its end-points, the labels of its vertices always increase. The weight of an increasing path, is the sum of the labels of its vertices. Determining lower bounds on the weight of the heaviest increasing path a point set always has.
We also study the problem of finding a non-crossing matching of the elements of \(P\) of maximum weight, where the weight of an edge with endpoints \(i, j \in P\) is \(\min\{i,j\}\).
For the entire collection see [Zbl 1253.68016].
Reviewer: Reviewer (Berlin)
MSC:
05A05 Permutations, words, matrices
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N., Rajagopalan, S., Suri, S.: Long non-crossing configurations in the plane. Fundamenta Informaticae 22, 385–394 (1995) · Zbl 0830.68001
[2] Chung, F.R.K.: On unimodal subsequences. J. Combin. Theory Ser. A 29, 267–279 (1980) · Zbl 0453.05003 · doi:10.1016/0097-3165(80)90021-7
[3] Dumitrescu, A., Tóth, C.: Long non-crossing configurations in the plane. Discrete Comput. Geom. 44, 727–752 (2010) · Zbl 1207.68416 · doi:10.1007/s00454-010-9277-9
[4] Erdos, P., Szekeres, G.: A combinatorial problem in geometry. Compositio Math. 2, 463–470 (1935) · Zbl 0012.27010
[5] Czyzowicz, J., Kranakis, E., Krizanc, D., Urrutia, J.: Maximal length common non-intersecting paths. In: Proc. Eighth Canadian Conference on Computational Geometry, Ottawa, pp. 180–189 (August 1996)
[6] Károlyi, G., Pach, J., Tóth, G.: Ramsey-type results for geometric graphs I. Discrete and Computational Geometry 18, 247–255 (1997) · Zbl 0940.05046 · doi:10.1007/PL00009317
[7] Sakai, T., Urrutia, J.: Monotonic Polygons and Paths in Weighted Point Sets. In: Akiyama, J., Bo, J., Kano, M., Tan, X. (eds.) CGGA 2010. LNCS, vol. 7033, pp. 164–175. Springer, Heidelberg (2011) · Zbl 1349.68298 · doi:10.1007/978-3-642-24983-9_17
[8] Tutte, W.T.: The quest of the perfect square. Amer. Math. Monthly 72, 29–35 (1965) · Zbl 0126.26302 · doi:10.2307/2313308
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.