×

Approximating the \(k\)-level in three-dimensional plane arrangements. (English) Zbl 1384.52022

Loebl, Martin (ed.) et al., A journey through discrete mathematics. A tribute to Jiří Matoušek. Cham: Springer (ISBN 978-3-319-44478-9/hbk; 978-3-319-44479-6/ebook). 467-503 (2017).
In the present paper, the authors provide a construction which allows to approximate the \((n/r)\)-level of an arrangement of \(n\) non-vertical hyperplanes in the three dimensions by a terrain consisting of \(O(r/\varepsilon^{3})\) triangular faces, which lies entirely between levels \(n/r\) and \((1+\varepsilon)n/r\), for a certain paramter \(r < n\). Let us recall that for a set of \(n\) non-vertical hyperplanes \(H\) in \(\mathbb{R}^{d}\) a \((1/r)\) cutting of the associated arrangement \(\mathcal{A}\) is a collection of pairwise openly disjoint simplices (or other regions of constant complexity) such that the closure of their union covers \(\mathbb{R}^{d}\), and each region is crossed by at most \(n/r\) hyperplanes. Next, the level of a point \(p\) in the arrangement \(\mathcal{A}\) is the number of hyperplanes lying vertically below it. For a given parameter \(0 \leq k \leq n-1\), the \(k\)-th level, denoted by \(L_{k}\), is the closure of all the points that lie on some hyperplane of \(H\) and are at level exactly \(k\). Moreover, \(\leq k\)-level, which is denoted by \(L_{\leq k}\), is the union of all the \(j\)-levels for \(j \in \{0,...,k\}\). A collection of pairwise openly disjoint simplices such that the closure of their union covers \(L_{\leq k}\) and such that each simplex is crossed by at most \(n/r\) hyperplanes of \(H\) is a \(k\)-shallow \((1/r)\)-cutting. The main question that we can ask is whether one can approximate a \(k\)-level of an arrangement of a set \(H\) of \(n\) hyperplanes in \(3\)-space. Being more precise, given \(k\) and \(\varepsilon >0\), we want to find a polyhedral terrain with a small number of faces, which lie entirely between the levels \(k\) and \((1+\varepsilon)k\) of the arrangement \(\mathcal{A}\). The first contribution of the authors is to give an alternative and constructive proof of the existence of optimal-size shallow cuttings in a three-dimensional plane arrangement by vertical semi-unbounded triangular prisms. This allows to prove the following result
Main Theorem. Let \(H\) be a set of \(n\) non-vertical planes in \(\mathbb{R}^{3}\) in general position and let \(k < n\), \(\varepsilon >0\) be given parameters. Put \(r = n/k\). Then there exists a \(k\)-shallow \(((1+\varepsilon)/r)\)-cutting of the associated hyperplane arrangement \(\mathcal{A}\) consisting of \(O(r/\varepsilon^{3})\) vertical prisms (unbounded from below). The top of each prism is a triangle or a wedge that is fully contained between levels \(k\) and \((1+\varepsilon)k\) of \(\mathcal{A}\), and these triangles form a polyhedral terrain.
For the entire collection see [Zbl 1383.05002].

MSC:

52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
51A05 General theory of linear incidence geometry and projective geometries
51A20 Configuration theorems in linear incidence geometry
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] P. Afshani, T.M. Chan, Optimal halfspace range reporting in three dimensions, in Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA) (2009), pp. 180-186 · Zbl 1422.68230
[2] P. Afshani, K. Tsakalidis, Optimal deterministic shallow cuttings for 3d dominance ranges, in Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA) (2014), pp. 1389-1398 · Zbl 1422.68232
[3] P. Afshani, C.H. Hamilton, N. Zeh, A general approach for cache-oblivious range reporting and approximate range counting. Comput. Geom. Theory Appl. 43(8), 700-712 (2010) · Zbl 1206.65068 · doi:10.1016/j.comgeo.2010.04.003
[4] P. Afshani, T.M. Chan, K. Tsakalidis, Deterministic rectangle enclosure and offline dominance reporting on the RAM, in Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP). Volume 8572 of Lecture Notes in Computer Science (Springer, 2014), pp. 77-88 · Zbl 1410.68360
[5] P.K. Agarwal, Partitioning arrangements of lines I: an efficient deterministic algorithm. Discrete Comput. Geom. 5, 449-483 (1990) · Zbl 0701.68035 · doi:10.1007/BF02187805
[6] P.K. Agarwal, Partitioning arrangements of lines: II. Applications. Discrete Comput. Geom. 5, 533-573 (1990) · Zbl 0709.68108 · doi:10.1007/BF02187809
[7] P.K. Agarwal, Geometric partitioning and its applications, in Computational Geometry: Papers from the DIMACS Special Year, ed. by J.E. Goodman, R. Pollack, W. Steiger (American Mathematical Society, Providence, 1991), pp. 1-37 · Zbl 0733.68081
[8] P.K. Agarwal, Intersection and Decomposition Algorithms for Planar Arrangements (Cambridge University Press, New York, 1991) · Zbl 0729.68082
[9] P.K. Agarwal, P.K. Desikan, An efficient algorithm for terrain simplification, in Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA) (1997), pp. 139-147 · Zbl 1321.68424
[10] P.K. Agarwal, J. Erickson, Geometric range searching and its relatives, in Advances in Discrete and Computational Geometry, ed. by B. Chazelle, J.E. Goodman, R. Pollack (American Mathematical Society, Providence, 1999), pp. 1-56 · Zbl 0916.68031
[11] P.K. Agarwal, J. Matoušek, Dynamic half-space range reporting and its applications. Algorithmica 13, 325-345 (1995) · Zbl 0827.68037 · doi:10.1007/BF01293483
[12] P.K. Agarwal, S. Suri, Surface approximation and geometric partitions. SIAM J. Comput. 27(4), 1016-1035 (1998) · Zbl 0911.65149 · doi:10.1137/S0097539794269801
[13] P.K. Agarwal, B. Aronov, T.M. Chan, M. Sharir, On levels in arrangements of lines, segments, planes, and triangles. Discrete Comput. Geom. 19, 315-331 (1998) · Zbl 0899.68106 · doi:10.1007/PL00009348
[14] B. Aronov, M. de Berg, E. Ezra, M. Sharir, Improved bounds for the union of locally fat objects in the plane. SIAM J. Comput. 43(2), 543-572 (2014) · Zbl 1295.05258 · doi:10.1137/120891241
[15] R.P. Bambah, C.A. Rogers, Covering the plane with convex sets. J. Lond. Math. Soc. 1(3), 304-314 (1952) · Zbl 0046.38004 · doi:10.1112/jlms/s1-27.3.304
[16] T.M. Chan, Random sampling, halfspace range reporting, and construction of ( ≤ k)-levels in three dimensions. SIAM J. Comput. 30(2), 561-575 (2000) · Zbl 0963.68207 · doi:10.1137/S0097539798349188
[17] T.M. Chan, Low-dimensional linear programming with violations. SIAM J. Comput. 34(4), 879-893 (2005) · Zbl 1075.68092 · doi:10.1137/S0097539703439404
[18] T.M. Chan, A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries. J. Assoc. Comput. Mach. 57(3), 1-15 (2010). Art. 16 · Zbl 1327.68314
[19] T.M. Chan, K. Tsakalidis, Optimal deterministic algorithms for 2-d and 3-d shallow cuttings, in Proceedings of the 31st International Annual Symposium on Computational Geometry (SoCG) (2015), pp. 719-732 · Zbl 1378.68165
[20] B. Chazelle, Cutting hyperplanes for divide-and-conquer. Discrete Comput. Geom. 9(2), 145-158 (1993) · Zbl 0784.52018 · doi:10.1007/BF02189314
[21] B. Chazelle, Cuttings (chapter 25), in Handbook of Data Structures and Applications, ed. by D.P. Mehta, S. Sahni (Chapman and Hall/CRC, Boca Raton, 2004) · Zbl 1387.68249
[22] B. Chazelle, J. Friedman, A deterministic view of random sampling and its use in geometry. Combinatorica 10(3), 229-249 (1990) · Zbl 0715.68036 · doi:10.1007/BF02122778
[23] B. Chazelle, H. Edelsbrunner, L.J. Guibas, M. Sharir, A singly-exponential stratification scheme for real semi-algebraic varieties and its applications. Theoret. Comput. Sci. 84, 77-105 (1991). Also in Proceedings of the 16th International Colloquium on Automata, Languages and Programming, pp. 179-193 · Zbl 0757.14031
[24] K.L. Clarkson, New applications of random sampling in computational geometry. Discrete Comput. Geom. 2, 195-222 (1987) · Zbl 0615.68037 · doi:10.1007/BF02187879
[25] K.L. Clarkson, P.W. Shor, Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4, 387-421 (1989) · Zbl 0681.68060 · doi:10.1007/BF02187740
[26] K.L. Clarkson, H. Edelsbrunner, L.J. Guibas, M. Sharir, E. Welzl, Combinatorial complexity bounds for arrangements of curves and spheres. Discrete Comput. Geom. 5, 99-160 (1990) · Zbl 0704.51003 · doi:10.1007/BF02187783
[27] E. Ezra, D. Halperin, M. Sharir, Speeding up the incremental construction of the union of geometric objects in practice. Comput. Geom. Theory Appl. 27(1), 63-85 (2004) · Zbl 1039.65019 · doi:10.1016/j.comgeo.2003.07.006
[28] G.N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput. 16(6), 1004-1022 (1987) · Zbl 0654.68087 · doi:10.1137/0216064
[29] S. Har-Peled, Constructing planar cuttings in theory and practice. SIAM J. Comput. 29(6), 2016-2039 (2000) · Zbl 0981.65027 · doi:10.1137/S0097539799350232
[30] S. Har-Peled, M. Sharir, Relative (p, ɛ)-approximations in geometry. Discrete Comput. Geom. 45(3), 462-496 (2011) · Zbl 1220.68106 · doi:10.1007/s00454-010-9248-1
[31] S. Har-Peled, H. Kaplan, M. Sharir, Approximating the k-level in three-dimensional plane arrangements, in Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA) (2016), pp. 1193-1212 · Zbl 1384.52022
[32] S. Har-Peled, H. Kaplan, M. Sharir, Approximating the k-level in three-dimensional plane arrangements. CoRR (2016). abs/1601.04755 · Zbl 1384.52022
[33] K. Kedem, R. Livne, J. Pach, M. Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discrete Comput. Geom. 1, 59-71 (1986) · Zbl 0594.52004 · doi:10.1007/BF02187683
[34] P.N. Klein, S. Mozes, C. Sommer, Structured recursive separator decompositions for planar graphs in linear time, in Proceedings of the 45th Annual ACM Symposium on Theory Computing (STOC) (2013), pp. 505-514 · Zbl 1293.05066
[35] V. Koltun, Almost tight upper bounds for vertical decompositions in four dimensions. J. Assoc. Comput. Mach. 51(5), 699-730 (2004) · Zbl 1204.68244 · doi:10.1145/1017460.1017461
[36] V. Koltun, M. Sharir, Curve-sensitive cuttings. SIAM J. Comput. 34(4), 863-878 (2005) · Zbl 1075.68093 · doi:10.1137/S0097539703435686
[37] R.J. Lipton, R.E. Tarjan, A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 177-189 (1979) · Zbl 0432.05022 · doi:10.1137/0136016
[38] J. Matoušek, Construction of ɛ-nets. Discrete Comput. Geom. 5, 427-448 (1990) · Zbl 0701.68040 · doi:10.1007/BF02187804
[39] J. Matoušek, Efficient partition trees. Discrete Comput. Geom. 8, 315-334 (1992) · Zbl 0752.68088 · doi:10.1007/BF02293051
[40] J. Matoušek, Range searching with efficient hierarchical cutting. Discrete Comput. Geom. 10, 157-182 (1992) · Zbl 0774.68101 · doi:10.1007/BF02573972
[41] J. Matoušek, Reporting points in halfspaces. Comput. Geom. Theory Appl. 2(3), 169-186 (1992) · Zbl 0772.68105 · doi:10.1016/0925-7721(92)90006-E
[42] J. Matoušek, On constants for cuttings in the plane. Discrete Comput. Geom. 20, 427-448 (1998) · Zbl 0912.68203 · doi:10.1007/PL00009394
[43] J. Matoušek, N. Miller, J. Pach, M. Sharir, S. Sifrony, E. Welzl, Fat triangles determine linearly many holes, in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) (1991), pp. 49-58 · Zbl 0802.68152
[44] G.L. Miller, Finding small simple cycle separators for 2-connected planar graphs. J. Comput. Syst. Sci. 32(3), 265-279 (1986) · Zbl 0607.05028 · doi:10.1016/0022-0000(86)90030-9
[45] K. Mulmuley, An efficient algorithm for hidden surface removal, II. J. Comput. Syst. Sci. 49, 427-453 (1994) · Zbl 0938.68947 · doi:10.1016/S0022-0000(05)80067-4
[46] N.H. Mustafa, R. Raman, S. Ray, Settling the APX-hardness status for geometric set cover, in Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2014), pp. 541-550
[47] J. Pach, P.K. Agarwal, Combinatorial Geometry (Wiley, New York, 1995) · Zbl 0881.52001 · doi:10.1002/9781118033203
[48] E.A. Ramos, On range reporting, ray shooting and k-level construction, in Proceedings of the 15th Annual Symposium on Computational Geometry (SoCG) (ACM, 1999), pp. 390-399
[49] R. Seidel, A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Comput. Geom. Theory Appl. 1, 51-64 (1991) · Zbl 0733.68092 · doi:10.1016/0925-7721(91)90012-4
[50] M. Sharir, P.K. Agarwal, Davenport-Schinzel Sequences and Their Geometric Applications (Cambridge University Press, New York, 1995) · Zbl 0834.68113
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.