More Web Proxy on the site http://driver.im/

research-article

Public Access

Threesomes, Degenerates, and Love Triangles

Authors:

Allan Grønlund,

Seth PettieAuthors Info & Claims

Journal of the ACM (JACM), Volume 65, Issue 4

Article No.: 22, Pages 1 - 25

https://doi.org/10.1145/3185378

Published: 24 April 2018 Publication History

Abstract

The 3SUM problem is to decide, given a set of n real numbers, whether any three sum to zero. It is widely conjectured that a trivial O(n²)-time algorithm is optimal on the Real RAM, and optimal even in the nonuniform linear decision tree model. Over the years the consequences of this conjecture have been revealed. This 3SUM conjecture implies Ω (n²) lower bounds on numerous problems in computational geometry, and a variant of the conjecture for integer inputs implies strong lower bounds on triangle enumeration, dynamic graph algorithms, and string matching data structures.

In this article, we refute the conjecture that 3SUM requires Ω (n²) in the Real RAM and refute more forcefully the conjecture that its complexity is Ω (n²) in the linear decision tree model. In particular, we prove that the decision tree complexity of 3SUM is O(n^3/2√ log n) and give two subquadratic 3SUM algorithms, a deterministic one running in O(n² / (log n/ log log n)^2/3) time and a randomized one running in O(n²(log log n)² / log n) time with high probability. Our results lead directly to improved bounds on the decision tree complexity of k-variate linear degeneracy testing for all odd k≥ 3.

Finally, we give a subcubic algorithm for a generalization of the (min,+)-product over real-valued matrices and apply it to the problem of finding zero-weight triangles in edge-weighted graphs. We give a depth-O(n^5/2√ log n) decision tree for this problem, as well as a deterministic algorithm running in time O(n³ (log log n)²/log n).

References

[1]

S. Aaronson and Y. Shi. 2004. Quantum lower bounds for the collision and the element distinctness problems. J. ACM 51, 4 (2004), 595--605.

Digital Library

[2]

A. Abboud, A. Backurs, and V. Vassilevska Williams. 2015. Tight hardness results for LCS and other sequence similarity measures. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS’15). 59--78.

Digital Library

[3]

A. Abboud, F. Grandoni, and V. Vassilevska Williams. 2015. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15). 1681--1697.

Digital Library

[4]

A. Abboud and V. V. Williams. 2014. Popular conjectures imply strong lower bounds for dynamic problems. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS’14). 434--443. Retrieved from

Digital Library

[5]

A. Abboud, V. Vassilevska Williams, and O. Weimann. 2014. Consequences of faster sequence alignment. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP’14). 39--51.

[6]

A. V. Aho, J. E. Hopcroft, and J. D. Ullman. 1975. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA.

Digital Library

[7]

O. Aichholzer, F. Aurenhammer, E. D. Demaine, F. Hurtado, P. Ramos, and J. Urrutia. 2012. On k-convex polygons. Comput. Geom. 45, 3 (2012), 73--87.

Digital Library

[8]

N. Ailon and B. Chazelle. 2005. Lower bounds for linear degeneracy testing. J. ACM 52, 2 (2005), 157--171.

Digital Library

[9]

N. Alon and R. B. Boppana. 1987. The monotone circuit complexity of boolean functions. Combinatorica 7, 1 (1987), 1--22.

Digital Library

[10]

A. Amir, T. M. Chan, M. Lewenstein, and N. Lewenstein. 2014. Consequences of faster sequence alignment. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP’14). 114--125.

[11]

A. Amir, T. Kopelowitz, A. Levy, S. Pettie, E. Porat, and B. R. Shalom. 2016. Mind the gap: Essentially optimal algorithms for online dictionary matching with one gap. In Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC’16). 12:1--12:12. Retrieved from

[12]

A. Backurs and P. Indyk. 2015. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC’15). 51--58.

Digital Library

[13]

I. Baran, E. D. Demaine, and M. Pǎtraşcu. 2008. Subquadratic algorithms for 3SUM. Algorithmica 50, 4 (2008), 584--596.

[14]

L. Barba, J. Cardinal, J. Iacono, S. Langerman, A. Ooms, and N. Solomon. 2017. Subquadratic algorithms for algebraic generalizations of 3SUM. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG’17). 13:1--13:15. Retrieved from

[15]

G. Barequet and S. Har-Peled. 2001. Polygon containment and translational min-Hausdorff-distance between segment sets are 3SUM-hard. Int. J. Comput. Geometry Appl. 11, 4 (2001), 465--474.

[16]

P. Beame. 1991. A general sequential time-space tradeoff for finding unique elements. SIAM J. Comput. 20, 2 (1991), 270--277. Retrieved from

Digital Library

[17]

C. H. Bennett, E. Bernstein, G. Brassard, and U. V. Vazirani. 1997. Strengths and weaknesses of quantum computing. SIAM J. Comput. 26, 5 (1997), 1510--1523.

Digital Library

[18]

A. Bjorklund, R. Pagh, V. Vassilevska Williams, and U. Zwick. 2014. Listing triangles. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP’14). 223--234.

[19]

M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan. 1973. Time bounds for selection. J. Comput. Syst. Sci. 7, 4 (1973), 448--461.

Digital Library

[20]

M. Braverman, Y. K. Ko, and O. Weinstein. 2015. Approximating the best nash equilibrium in n<sup>o(log n)</sup>-time breaks the exponential time hypothesis. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15). 970--982.

Digital Library

[21]

D. Bremner, T. M. Chan, E. D. Demaine, J. Erickson, F. Hurtado, J. Iacono, S. Langerman, M. Pǎtraşcu, and P. Taslakian. 2014. Necklaces, convolutions, and X + Y. Algorithmica 69 (2014), 294--314.

[22]

K. Bringmann. 2014. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS’14). 661--670.

Digital Library

[23]

K. Bringmann and M. Künnemann. 2015. Quadratic conditional lower bounds for string problems and dynamic time warping. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS’15). 79--97.

Digital Library

[24]

R. C. Buck. 1943. Partition of space. Amer. Math. Monthly 50 (1943), 541--544.

[25]

A. Butman, P. Clifford, R. Clifford, M. Jalsenius, N. Lewenstein, B. Porat, E. Porat, and B. Sach. 2013. Pattern matching under polynomial transformation. SIAM J. Comput. 42, 2 (2013), 611--633.

[26]

C. Calabro, R. Impagliazzo, and R. Paturi. 2009. The complexity of satisfiability of small depth circuits. In Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC’09). 75--85. Retrieved from

[27]

M. L. Carmosino, J. Gao, R. Impagliazzo, I. Mihajlin, R. Paturi, and S. Schneider. 2016. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS’16). 261--270. Retrieved from

Digital Library

[28]

T. M. Chan. 2008. All-pairs shortest paths with real weights in O (n<sup>3</sup>/log n) time. Algorithmica 50, 2 (2008), 236--243.

Digital Library

[29]

T. M. Chan. 2015. Speeding up the four russians algorithm by about one more logarithmic factor. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15). 212--217.

Digital Library

[30]

T. M. Chan. 2018. 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). 881--897. Retrieved from

Digital Library

[31]

T. M. Chan and M. Lewenstein. 2015. Clustered integer 3SUM via additive combinatorics. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC’15). 31--40.

Digital Library

[32]

S. Chechik, D. Larkin, L. Roditty, G. Schoenebeck, R. E. Tarjan, and V. Vassilevska Williams. 2014. Better approximation algorithms for the graph diameter. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’14). 1041--1052.

Digital Library

[33]

K.-Y. Chen, P.-H. Hsu, and K.-M. Chao. 2009. Approximate matching for run-length encoded strings is 3SUM-hard. In Combinatorial Pattern Matching. Lecture Notes in Computer Science, Vol. 5577. Springer, 168--179.

[34]

N. Chiba and T. Nishizeki. 1985. Arboricity and subgraph listing algorithms. SIAM J. Comput. 14, 1 (1985), 210--223.

Digital Library

[35]

R. Duan and S. Pettie. 2010. Connectivity oracles for failure prone graphs. In Proceedings of the 42nd ACM Symposium on Theory of Computing. 465--474.

Digital Library

[36]

R. Duan and S. Pettie. 2017. Connectivity oracles for graphs subject to vertex failures. In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA’17). 490--509.

Digital Library

[37]

D. P. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.

Digital Library

[38]

H. Edelsbrunner, J. O’Rourke, and R. Seidel. 1986. Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput. 15, 2 (1986), 341--363.

Digital Library

[39]

J. Erickson. 1999. Bounds for linear satisfiability problems. Chicago J. Theor. Comput. Sci. 1999, 8 (1999).

[40]

M. L. Fredman. 1976. How good is the information theory bound in sorting? Theor. Comput. Sci. 1, 4 (1976), 355--361.

[41]

M. L. Fredman. 1976. New bounds on the complexity of the shortest path problem. SIAM J. Comput. 5, 1 (1976), 83--89.

Digital Library

[42]

M. L. Fredman and M. Saks. 1989. The cell probe complexity of dynamic data structures. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC’89). 345--354.

Digital Library

[43]

A. Freund. 2017. Improved subquadratic 3SUM. Algorithmica 77, 2 (2017), 440--458. Retrieved from

Digital Library

[44]

A. Gajentaan and M. H. Overmars. 1995. On a class of O/(n<sup>2</sup>) problems in computational geometry. Comput. Geom. 5 (1995), 165--185.

Digital Library

[45]

O. Gold and M. Sharir. 2017. Improved bounds for 3SUM, k-SUM, and linear degeneracy. In Proceedings of the 25th Annual European Symposium on Algorithms (ESA’17) (Leibniz International Proceedings in Informatics (LIPIcs)), Kirk Pruhs and Christian Sohler (Eds.), Vol. 87. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 42:1--42:13. Retrieved from

[46]

A. Grønlund and S. Pettie. 2014. Threesomes, degenerates, and love triangles. In Proceedings of the 55th IEEE Symposium on Foundations of Computer Science (FOCS’14). 621--630.

Digital Library

[47]

J. Hartmanis and R. E. Stearns. 1965. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117 (1965), 285--306.

[48]

J. Håstad. 1986. Almost optimal lower bounds for small depth circuits. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC’86). 6--20.

Digital Library

[49]

M. Henzinger, S. Krinninger, D. Nanongkai, and T. Saranurak. 2015. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC’15). 21--30.

Digital Library

[50]

R. Impagliazzo, S. Lovett, R. Paturi, and S. Schneider. 2014. 0-1 integer linear programming with a linear number of constraints. Electron. Colloq. Comput. Complex. (ECCC) 21 (2014), 24.

[51]

R. Impagliazzo and R. Paturi. 2001. On the complexity of k-SAT. J. Comput. Syst. Sci. 62, 2 (2001), 367--375.

Digital Library

[52]

R. Impagliazzo, R. Paturi, and F. Zane. 2001. Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63, 4 (2001), 512--530.

Digital Library

[53]

Z. Jafargholi and E. Viola. 2016. 3SUM, 3XOR, triangles. Algorithmica 74, 1 (2016), 326--343. Retrieved from

Digital Library

[54]

D. Kane, S. Lovett, and S. Moran. 2018. Near-optimal linear decision trees for k-SUM and related problems. In Proceedings of the 50th ACM Symposium on Theory of Computing (STOC’18).

[55]

T. Kopelowitz, S. Pettie, and E. Porat. 2015. Dynamic set intersection. In Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS’15). 470--481.

[56]

T. Kopelowitz, S. Pettie, and E. Porat. 2016. Higher lower bounds from the 3SUM conjecture. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’16). 1272--1287. Retrieved from

Digital Library

[57]

K. G. Larsen. 2012. The cell probe complexity of dynamic range counting. In Proceedings of the 44th Symposium on Theory of Computing Conference (STOC’12). 85--94.

Digital Library

[58]

A. Lincoln, V. Vassilevska Williams, J. R. Wang, and R. R. Williams. 2016. Deterministic time-space trade-offs for k-SUM. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP’16). 58:1--58:14. Retrieved from

[59]

S. Meiser. 1993. Point location in arrangements of hyperplanes. Inf. Comput. 106, 2 (1993), 286--303.

Digital Library

[60]

F. Meyer auf der Heide. 1984. A polynomial linear search algorithm for the n-dimensional knapsack problem. J. ACM 31, 3 (1984), 668--676.

Digital Library

[61]

C. St. J. A. Nash-Williams. 1964. Decomposition of finite graphs into forests. J. London Math. Soc. 39 (1964), 12.

[62]

M. Pǎtraşcu and E. Demaine. 2006. Logarithmic lower bounds in the cell-probe model. SIAM J. Comput. 35, 4 (2006), 932--963.

Digital Library

[63]

F. P. Preparata and M. I. Shamos. 1985. Computational Geometry. Springer, New York.

Digital Library

[64]

M. Pǎtraşcu. 2010. Towards polynomial lower bounds for dynamic problems. In Proceedings 42nd ACM Symposium on Theory of Computing (STOC’10). 603--610.

Digital Library

[65]

M. Pǎtraşcu and R. Williams. 2010. On the possibility of faster SAT algorithms. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’10). 1065--1075.

Digital Library

[66]

A. A. Razborov. 1985. Lower bounds for the monotone complexity of some boolean functions. Dokl. Ak. Nauk. USSR 281 (1985), 798--801(in Russian). English translation in Sov. Math. Dokl. 31 (1985): 354--357.

[67]

L. Roditty and V. Vassilevska Williams. 2013. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proceedings of the 45th ACM Symposium on Theory of Computing (STOC’13). 515--524.

Digital Library

[68]

B. Saha. 2015. Language edit distance and maximum likelihood parsing of stochastic grammars: Faster algorithms and connection to fundamental graph problems. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS’15). 118--135. Retrieved from

Digital Library

[69]

M. A. Soss, J. Erickson, and M. H. Overmars. 2003. Preprocessing chains for fast dihedral rotations is hard or even impossible. Comput. Geom. 26, 3 (2003), 235--246.

Digital Library

[70]

V. Vassilevska Williams and R. Williams. 2010. Subcubic equivalences between path, matrix and triangle problems. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS’10). 645--654.

Digital Library

[71]

V. Vassilevska Williams and R. Williams. 2013. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput. 42, 3 (2013), 831--854.

Cited By

Chan TZheng D(2024)Hopcroft’s Problem, Log* Shaving, Two-dimensional Fractional Cascading, and Decision TreesACM Transactions on Algorithms10.1145/359135720:3(1-27)Online publication date: 21-Jun-2024
https://dl.acm.org/doi/10.1145/3591357
Cardinal JSharir M(2024)Improved Algebraic Degeneracy TestingDiscrete & Computational Geometry10.1007/s00454-024-00673-7Online publication date: 25-Jun-2024
https://doi.org/10.1007/s00454-024-00673-7
Agrawal SSaha SSchwartzbach NVanukuri AVasudevan P(2024)k-SUM in the Sparse Regime: Complexity and ApplicationsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68379-4_10(315-351)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68379-4_10
Show More Cited By

Index Terms

Threesomes, Degenerates, and Love Triangles
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
2. Theory of computation
  1. Computational complexity and cryptography
    1. Oracles and decision trees

Recommendations

More Logarithmic-factor Speedups for 3SUM, (median,+)-convolution, and Some Geometric 3SUM-hard Problems
Special Issue on Soda'18 and Regular Papers

This article presents an algorithm that solves the 3SUM problem for n real numbers in O((n²/ log²n)(log log n)^O(1)) time, improving previous solutions by about a logarithmic factor. Our framework for shaving off two logarithmic factors can be applied to ...
Clustered Integer 3SUM via Additive Combinatorics
STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

We present a collection of new results on problems related to 3SUM, including: The first truly subquadratic algorithm for computing the (min,+) convolution for monotone increasing sequences with integer values bounded by O(n), solving 3SUM for monotone ...
Towards polynomial lower bounds for dynamic problems
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

We consider a number of dynamic problems with no known poly-logarithmic upper bounds, and show that they require n^Ω(1) time per operation, unless 3SUM has strongly subquadratic algorithms. Our result is modular: (1) We describe a carefully-chosen ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 65, Issue 4

Distributed Computing, Cryptography, Distributed Computing, Cryptography, Coding Theory, Automata Theory, Complexity Theory, Programming Languages, Algorithms, Invited Paper Foreword and Databases

August 2018

307 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/3208081

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 April 2018

Accepted: 01 February 2018

Revised: 01 September 2017

Received: 01 August 2015

Published in JACM Volume 65, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Danish National Research Foundation
National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
1,092
Total Downloads

Downloads (Last 12 months)193
Downloads (Last 6 weeks)11

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chan TZheng D(2024)Hopcroft’s Problem, Log* Shaving, Two-dimensional Fractional Cascading, and Decision TreesACM Transactions on Algorithms10.1145/359135720:3(1-27)Online publication date: 21-Jun-2024
https://dl.acm.org/doi/10.1145/3591357
Cardinal JSharir M(2024)Improved Algebraic Degeneracy TestingDiscrete & Computational Geometry10.1007/s00454-024-00673-7Online publication date: 25-Jun-2024
https://doi.org/10.1007/s00454-024-00673-7
Agrawal SSaha SSchwartzbach NVanukuri AVasudevan P(2024)k-SUM in the Sparse Regime: Complexity and ApplicationsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68379-4_10(315-351)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68379-4_10
Chan TVassilevska Williams VXu YSaha BServedio R(2023)Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and MoreProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585237(419-432)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585237
Chan TJin CWilliams VXu Y(2023)Faster Algorithms for Text-to-Pattern Hamming Distances2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00136(2188-2203)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00136
Cordier MWheeler M(2023)Searching for Point Locations Using LinesThe College Mathematics Journal10.1080/07468342.2023.226307454:5(423-433)Online publication date: 23-Oct-2023
https://doi.org/10.1080/07468342.2023.2263074
Aronov BEzra ESharir MZigdon G(2023)Time and space efficient collinearity indexingComputational Geometry: Theory and Applications10.1016/j.comgeo.2022.101963110:COnline publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.comgeo.2022.101963
Aronov Bde Berg MCardinal JEzra EIacono JSharir M(2023)Subquadratic algorithms for some 3Sum-hard geometric problems in the algebraic decision-tree modelComputational Geometry: Theory and Applications10.1016/j.comgeo.2022.101945109:COnline publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1016/j.comgeo.2022.101945
Chan TWilliams VXu YLeonardi SGupta A(2022)Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OVProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520032(1501-1514)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520032
Aronov BEzra ESharir M(2022)Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets: Collinearity Testing and Related ProblemsDiscrete & Computational Geometry10.1007/s00454-022-00437-168:4(997-1048)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s00454-022-00437-1
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents