×

A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model. (English) Zbl 1415.52017

Summary: We consider the point location problem in an arrangement of \(n\) arbitrary hyperplanes in any dimension \(d\), in the linear decision tree model, in which we only count linear comparisons involving the query point, and all other operations do not explicitly access the query and are for free. We mainly consider the simpler variant (which arises in many applications) where we only want to determine whether the query point lies on some input hyperplane. We present an algorithm that performs a point location query with \(O(d^2\log n)\) linear comparisons, improving the previous best result by about a factor of \(d\). Our approach is a variant of S. Meiser’s technique for point location [Inf. Comput. 106, No. 2, 286–303 (1993; Zbl 0781.68121)] (see also J. Cardinal et al. [LIPIcs – Leibniz Int. Proc. Inform. 57, Article 25, 17 p. (2016; Zbl 1397.68093)]), and its improved performance is due to the use of vertical decompositions in an arrangement of hyperplanes in high dimensions, rather than bottom-vertex triangulation used in the earlier approaches. The properties of such a decomposition, both combinatorial and algorithmic (in the standard real RAM model), are developed in a companion paper [E. Ezra et al., “Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location”, Preprint, arXiv:1712.02913], and are adapted here (in simplified form) for the linear decision tree model. Several applications of our algorithm are presented, such as the \(k\)-SUM problem and the Knapsack and SubsetSum problems. However, these applications have been superseded by the more recent result of D. M. Kane et al. [“Near-optimal linear decision trees for \(k\)-SUM and related problems”, in: Proceedings of the 50th ACM symposium on theory of computing (STOC’15), 25–29 June, 2018. New York: ACM. 554–563 (2018; doi:10.1145/3188745.3188770)], obtained after the original submission (and acceptance) of the conference version of our paper [the authors, LIPIcs – Leibniz Int. Proc. Inform. 77, Article 41, 15 p. (2017; Zbl 1432.68178)]. This result only applies to ‘low-complexity’ hyperplanes (for which the \(\ell _1\)-norm of their coefficient vector is a small integer), which arise in the aforementioned applications. Still, our algorithm has currently the best performance for arbitrary hyperplanes.

MSC:

52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
52C45 Combinatorial complexity of geometric structures
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agarwal, PK; Sharir, M.; Sack, J. (ed.); Urrutia, J. (ed.), Arrangements and their applications, 973-1027 (2000), Amsterdam
[2] Ailon, N., Chazelle, B.: Lower bounds for linear degeneracy testing. J. ACM 52(2), 157-171 (2005) · Zbl 1286.68172 · doi:10.1145/1059513.1059515
[3] Cardinal, J., Iacono, J., Ooms, A.: Solving \[k\] k-SUM using few linear queries. In: Sankowski, P., Zaroliagis, C. (eds.) Proceedings of the 24th European Symposium on Algorithms. LIPIcs. Leibniz International Proceedings in Informatics, vol. 57, pp. 25:1-25:17. Schloss Dagstuhl. Leibniz-Zentrum für Informatik, Wadern (2016) · Zbl 1397.68093
[4] Chan, T.M.: More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’18), pp. 881-897. SIAM, Philadelphia (2018) · Zbl 1403.68378
[5] Chan, T.M., Lewenstein, M.: Clustered integer 3SUM via additive combinatorics. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC’15), pp. 31-40. ACM, New York (2015) · Zbl 1321.68299
[6] Chazelle, B., Friedman, J.: A deterministic view of random sampling and its use in geometry. Combinatorica 10(3), 229-249 (1990) · Zbl 0715.68036 · doi:10.1007/BF02122778
[7] Chazelle, B., Edelsbrunner, H., Guibas, L.J., Sharir, M.: A singly exponential stratification scheme for real semi-algebraic varieties and its applications. Theor. Comput. Sci. 84(1), 77-105 (1991). Also in: Proceedings of the 16th International Colloquium on Automata, Languages and Programming (ICALP’89), pp. 179-193 (1989) · Zbl 0757.14031
[8] Clarkson, K.L.: New applications of random sampling in computational geometry. Discrete Comput. Geom. 2(2), 195-222 (1987) · Zbl 0615.68037 · doi:10.1007/BF02187879
[9] Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry. II. Discrete Comput. Geom. 4(5), 387-421 (1989) · Zbl 0681.68060 · doi:10.1007/BF02187740
[10] Dobkin, D., Lipton, R.J.: A lower bound of \[n^2/2\] n2/2 on linear search programs for the knapsack problem. J. Comput. Syst. Sci. 16(3), 413-417 (1978) · Zbl 0397.68045 · doi:10.1016/0022-0000(78)90026-0
[11] Dobkin, D., Lipton, R.J.: On the complexity of computations under varying set of primitives. J. Comput. Syst. Sci. 18(1), 86-91 (1979) · Zbl 0409.68023 · doi:10.1016/0022-0000(79)90054-0
[12] Erickson, J.: Lower bounds for linear satisfiability problems. In: Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 388-395. San Francisco, California (1995) · Zbl 0849.68041
[13] Ezra, E., Sharir, M.: A nearly quadratic bound for the decision tree complexity of \[k\] k-SUM. In: Aronov, B., Katz, M.J. (eds.) Proceedings of the 33rd International Symposium on Computational Geometry (SoCG’17). Leibniz International Proceedings in Informatics, vol. 77, pp. 41:1-41:15. Schloss Dagstuhl. Leibniz-Zentrum für Informatik, Wadern (2017) · Zbl 1432.68178
[14] Ezra, E., Har-Peled, S., Kaplan, H., Sharir, M.: Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location (2017). arXiv:1712.02913 · Zbl 1442.52020
[15] Freund, A.: Improved subquadratic 3SUM. Algorithmica 77(2), 440-458 (2017) · Zbl 1359.68130 · doi:10.1007/s00453-015-0079-6
[16] Gajentaan, A., Overmars, M.H.: On a class of \[{O}(n^2)O\](n2) problems in computational geometry. Comput. Geom. 5(3), 165-185 (1995) · Zbl 0839.68105 · doi:10.1016/0925-7721(95)00022-2
[17] Gold, O., Sharir, M.: Improved bounds for 3SUM, \[k\] k-SUM, and linear degeneracy. In: Pruhs, K., Sohler, C. (eds.) Proceedings of the 25th European Symposium on Algorithms (ESA’17). LIPIcs. Leibniz International Proceedings in Informatics, vol. 87, pp. 42:1-42:13. Schloss Dagstuhl. Leibniz-Zentrum für Informatik, Wadern (2017). Also in arXiv:1512.05279v2 · Zbl 1442.68070
[18] Grønlund, A., Pettie, S.: Threesomes, degenerates, and love triangles. In: Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS’14), pp. 621-630. IEEE, Los Alamitos (2014) · Zbl 1422.68112
[19] Guibas, L.J., Halperin, D., Matoušek, J., Sharir, M.: Vertical decomposition of arrangements of hyperplanes in four dimensions. Discrete Comput. Geom. 14(2), 113-122 (1995) · Zbl 0832.68076 · doi:10.1007/BF02570698
[20] Har-Peled, S.: Geometric Approximation Algorithms. Mathematical Surveys and Monographs, vol. 173. American Mathematical Society, Providence (2011) · Zbl 1230.68215
[21] Haussler, D., Welzl, E.: \[ \varepsilon\] ε-nets and simplex range queries. Discrete Comput. Geom. 2(2), 127-151 (1987) · Zbl 0619.68056 · doi:10.1007/BF02187876
[22] Kane, D.M., Lovett, S., Moran, S.: Near-optimal linear decision trees for \[k\] k-SUM and related problems. In: Proceedings of the 50th ACM Symposium on Theory of Computing (STOC’15), pp. 554-563. ACM, New York (2018) · Zbl 1428.68129
[23] Kane, D.M., Lovett, S., Moran, S.: Generalized comparison trees for point-location problems. In: Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP’18), vol. 82:1-82:13 (2018) · Zbl 1499.68080
[24] Koltun, V.: Sharp bounds for vertical decompositions of linear arrangements in four dimensions. Discrete Comput. Geom. 31(3), 435-460 (2004) · Zbl 1065.52019 · doi:10.1007/s00454-003-2871-3
[25] Liu, D.: A note on point location in arrangements of hyperplanes. Inf. Process. Lett. 90(2), 93-95 (2004) · Zbl 1177.68241 · doi:10.1016/j.ipl.2004.01.010
[26] Matoušek, J.: Cutting hyperplane arrangements. Discrete Comput. Geom. 6(5), 385-406 (1991) · Zbl 0765.68210 · doi:10.1007/BF02574697
[27] Matoušek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, New York (2002) · Zbl 0999.52006
[28] Meiser, S.: Point location in arrangements of hyperplanes. Inf. Comput. 106(2), 286-303 (1993) · Zbl 0781.68121 · doi:10.1006/inco.1993.1057
[29] Meyer auf der Heide, F.: A polynomial linear search algorithm for the \[n\] n-dimensional knapsack problem. J. ACM 31(3), 668-676 (1984) · Zbl 0631.68037 · doi:10.1145/828.322450
[30] VanArsdale, D.: Homogeneous transformation matrices for computer graphics. Comput. Graphics 18(2), 177-191 (1994) · doi:10.1016/0097-8493(94)90092-2
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.