Abstract
Let P be a set of n points in the plane. We consider a variation of the classical Erdős-Szekeres problem, presenting efficient algorithms with \(O(n^3)\) running time and \(O(n^2)\) space complexity that compute: (1) A subset S of P such that the boundary of the rectilinear convex hull of S has the maximum number of points from P, (2) a subset S of P such that the boundary of the rectilinear convex hull of S has the maximum number of points from P and its interior contains no element of P, (3) a subset S of P such that the rectilinear convex hull of S has maximum area and its interior contains no element of P, and (4) when each point of P is assigned a weight, positive or negative, a subset S of P that maximizes the total weight of the points in the rectilinear convex hull of S.
D. Orden—Research supported by project MTM2017-83750-P of the Spanish Ministry of Science (AEI/FEDER, UE).
P. Pérez-Lantero—Research supported by project CONICYT FONDECYT/Regular 1160543 (Chile).
D. Rappaport—Research supported by NSERC of Canada Discovery Grant RGPIN/06662-2015.
C. Seara—Research supported by projects MTM2015-63791-R MINECO/FEDER and Gen. Cat. DGR 2017SGR1640.
J. Tejel—Research supported by projects MTM2015-63791-R MINECO/FEDER and Gobierno de Aragón E41-17R.
J. Urrutia—Research supported by PAPIIT grant IN102117 from UNAM.
This work has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The notation \(\mathcal {RH}(P)\) is also used for the rectilinear convex hull [4].
- 2.
We note that using not so trivial methods, we can calculate all of the \(C_{p,q}\)’s in \(O(n^2\log n)\) time. However, this yields no improvement on the overall time complexity of our algorithms.
References
Aichholzer, O., et al.: On \(k\)-gons and \(k\)-holes in point sets. Comput. Geom. 48(7), 528–537 (2015)
Aichholzer, O., et al.: \(4\)-holes in point sets. Comput. Geom. 47(6), 644–650 (2014)
Aichholzer, O., Fabila-Monroy, R., Hackl, T., Huemer, C., Pilz, A., Vogtenhuber, B.: Lower bounds for the number of small convex \(k\)-holes. Comput. Geom. 47(5), 605–613 (2014)
Alegría-Galicia, C., Orden, D., Seara, C., Urrutia, J.: Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations. CoRR, abs/1710.10888 (2017)
Avis, D., Rappaport, D.: Computing the largest empty convex subset of a set of points. In: Proceedings of the 1st Annual Symposium on Computational Geometry, pp. 161–167 (1985)
Bautista-Santiago, C., Díaz-Báñez, J.M., Lara, D., Pérez-Lantero, P., Urrutia, J., Ventura, I.: Computing optimal islands. Oper. Res. Lett. 39(4), 246–251 (2011)
Brass, P., Moser, W., Pach, J.: Convex polygons and the Erdős-Szekeres problem. In: Chapter 8.2 in the Book Research Problems in Discrete Geometry. Springer (2005)
Chvátal, V., Klincsek, G.: Finding largest convex subsets. Congr. Numer. 29, 453–460 (1980)
Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463–470 (1935)
Fink, E., Wood, D.: Restricted-Orientation Convexity. Monographs in Theoretical Computer Science (An EATCS Series). Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-642-18849-7
Morris, W., Soltan, V.: The Erdős-Szekeres problem on points in convex position-a survey. Bull. Am. Math. Soc. 37(4), 437–458 (2000)
Ottmann, T., Soisalon-Soininen, E., Wood, D.: On the definition and computation of rectilinear convex hulls. Inf. Sci. 33(3), 157–171 (1984)
Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, Heidelberg (2012). https://doi.org/10.1007/978-1-4612-1098-6
Rawlins, G.J.E., Wood, D.: Ortho-convexity and its generalizations. Mach. Intell. Pattern Recognit. 6, 137–152 (1988)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
González-Aguilar, H. et al. (2019). Maximum Rectilinear Convex Subsets. In: Gąsieniec, L., Jansson, J., Levcopoulos, C. (eds) Fundamentals of Computation Theory. FCT 2019. Lecture Notes in Computer Science(), vol 11651. Springer, Cham. https://doi.org/10.1007/978-3-030-25027-0_19
Download citation
DOI: https://doi.org/10.1007/978-3-030-25027-0_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-25026-3
Online ISBN: 978-3-030-25027-0
eBook Packages: Computer ScienceComputer Science (R0)