×

zbMATH — the first resource for mathematics

Rectilinear convex hull with minimum area. (English) Zbl 1374.68632
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, 226-235 (2012).
Summary: Let \(P\) be a set of \(n\) points in the plane. We solve the problem of computing an orientation of the plane for which the rectilinear convex hull of \(P\) has minimum area in optimal \(\Theta (n\log n)\) time and \(O(n)\) space.
For the entire collection see [Zbl 1253.68016].

MSC:
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Avis, D., Beresford-Smith, B., Devroye, L., Elgindy, H., Guévremont, E., Hurtado, F., Zhu, B.: Unoriented \(\Theta\)-maxima in the plane: complexity and algorithms. SIAM J. Comput. 28(1), 278–296 (1999) · Zbl 0914.68102 · doi:10.1137/S0097539794277871
[2] Bae, S.W., Lee, C., Ahn, H.-K., Choi, S., Chwa, K.-Y.: Computing minimum-area rectilinear convex hull and L-shape. Computational Geometry: Theory and Applications 42(3), 903–912 (2009) · Zbl 1175.49035 · doi:10.1016/j.comgeo.2009.02.006
[3] Bentley, J., Ottmann, T.: Algorithms for reporting and counting geometric intersections. IEEE Trans. Computers C-28, 643–647 (1979) · Zbl 0414.68074 · doi:10.1109/TC.1979.1675432
[4] Biedl, T., Genç, B.: Reconstructing orthogonal polyhedra from putative vertex sets. Computational Geometry: Theory and Applications 44(8), 409–417 (2011) · Zbl 1225.65026 · doi:10.1016/j.comgeo.2011.04.002
[5] Biswas, A., Bhowmick, P., Sarkar, M., Bhattacharya, B.B.: Finding the Orthogonal Hull of a Digital Object: A Combinatorial Approach. In: Brimkov, V.E., Barneva, R.P., Hauptman, H.A. (eds.) IWCIA 2008. LNCS, vol. 4958, pp. 124–135. Springer, Heidelberg (2008) · Zbl 05259087 · doi:10.1007/978-3-540-78275-9_11
[6] Díaz-Báñez, J.M., López, M.A., Mora, M., Seara, C., Ventura, I.: Fitting a two-joint orthogonal chain to a point set. Computational Geometry: Theory and Applications 44(3), 135–147 (2011) · Zbl 1209.65019 · doi:10.1016/j.comgeo.2010.07.005
[7] Fink, E., Wood, D.: Strong restricted-orientation convexity. Geometriae Dedicata 69, 35–51 (1998) · Zbl 0899.52001 · doi:10.1023/A:1004973709260
[8] Franěk, V., Matousěk, J.: Computing D-convex hulls in the plane. Computational Geometry: Theory and Applications 42, 81–89 (2009) · Zbl 1159.65022 · doi:10.1016/j.comgeo.2008.03.003
[9] Khamsi, M.A., Kirk, W.A.: An introduction to metric spaces and fixed point theory. Wiley-Interscience (2001) · Zbl 1318.47001 · doi:10.1002/9781118033074
[10] Kung, H.T., Luccio, F., Preparata, F.P.: On finding the maxima of a set of vectors. Journal of the ACM 22, 469–476 (1975) · Zbl 0316.68030 · doi:10.1145/321906.321910
[11] Martynchik, V., Metelski, N., Wood, D.: O-convexity: computing hulls, approximations, and orientation sets. In: Canadian Conference on Computational Geometry, pp. 2–7 (1996)
[12] Matoušek, J., Plecháč, P.: On functional separately convex hulls. Discrete and Computational Geometry 19, 105–130 (1998) · Zbl 0892.68102 · doi:10.1007/PL00009331
[13] Ottman, T., Soisalon-Soisinen, E., Wood, D.: On the definition and computation of rectilinear convex hulls. Information Sciences 33, 157–171 (1984) · Zbl 0558.68061 · doi:10.1016/0020-0255(84)90025-2
[14] Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer (1985) · Zbl 0575.68059 · doi:10.1007/978-1-4612-1098-6
[15] Rawlins, G.J.E., Wood, D.: Ortho-convexity and its generalizations. In: Computational Morphology: A Computational Geometric Approach to the Analysis of Form, pp. 137–152. Elseiver Science Publishers B.V., North-Holland (1988) · doi:10.1016/B978-0-444-70467-2.50015-1
[16] Uchoa, E., De Aragão, M.P., Ribeiro, C.C.: Preprocessing Steiner problems from VLSI layout. Networks 40(1), 38–50 (2002) · Zbl 1064.68007 · doi:10.1002/net.10035
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.