{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:42Z","timestamp":1740109602838,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,11,25]],"date-time":"2023-11-25T00:00:00Z","timestamp":1700870400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,11,25]],"date-time":"2023-11-25T00:00:00Z","timestamp":1700870400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1564473"],"award-info":[{"award-number":["DMS-1564473"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["HR0011-16-C-0028"],"award-info":[{"award-number":["HR0011-16-C-0028"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textbf{p}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>p<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> be a configuration of <jats:italic>n<\/jats:italic> points in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbb R^d$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>R<\/mml:mi>\n                    <mml:mi>d<\/mml:mi>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for some <jats:italic>n<\/jats:italic> and some <jats:inline-formula><jats:alternatives><jats:tex-math>$$d \\ge 2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Each pair of points defines an edge, which has a Euclidean length in the configuration. A path is an ordered sequence of the points, and a loop is a path that begins and ends at the same point. A path or loop, as a sequence of edges, also has a Euclidean length, which is simply the sum of its Euclidean edge lengths. We are interested in reconstructing <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textbf{p}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>p<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> given a set of edge, path and loop lengths. In particular, we consider the unlabeled setting where the lengths are given simply as a set of real numbers, and are not labeled with the combinatorial data describing which paths or loops gave rise to these lengths. In this paper, we study the question of when <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textbf{p}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>p<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> will be uniquely determined (up to an unknowable Euclidean transform) from some given set of path or loop lengths through an exhaustive trilateration process. Such a process has already been used for the simpler problem of reconstruction using unlabeled edge lengths. This paper also provides a complete proof that this process must work in that edge-setting when given a sufficiently rich set of edge measurements and assuming that <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textbf{p}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>p<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is generic.<\/jats:p>","DOI":"10.1007\/s00454-023-00605-x","type":"journal-article","created":{"date-parts":[[2023,11,25]],"date-time":"2023-11-25T21:29:45Z","timestamp":1700947785000},"page":"399-441","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Trilateration Using Unlabeled Path or Loop Lengths"],"prefix":"10.1007","volume":"71","author":[{"given":"Ioannis","family":"Gkioulekas","sequence":"first","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Steven J.","family":"Gortler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5282-4800","authenticated-orcid":false,"given":"Louis","family":"Theran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Todd","family":"Zickler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,11,25]]},"reference":[{"key":"605_CR1","doi-asserted-by":"publisher","unstructured":"Anning, N.H., Erd\u00f6s, P.: Integral distances. Bull. Amer. Math. Soc. 51, 598\u2013600 (1945). ISSN 0002-9904. https:\/\/doi.org\/10.1090\/S0002-9904-1945-08407-9. http:\/\/dx.doi.org\/10.1090\/S0002-9904-1945-08407-9","DOI":"10.1090\/S0002-9904-1945-08407-9"},{"key":"605_CR2","doi-asserted-by":"publisher","unstructured":"Asimow, L., Roth, B.: The rigidity of graphs. Trans. Am. Math. Soc. 245, 279\u2013289 (1978). ISSN 0002-9947. https:\/\/doi.org\/10.2307\/1998867","DOI":"10.2307\/1998867"},{"key":"605_CR3","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Algorithms in real algebraic geometry, volume\u00a010 of Algorithms and Computation in Mathematics. Springer, Berlin, 2nd Edn (2006). ISBN 978-3-540-33098-1; 3-540-33098-4"},{"issue":"1","key":"605_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L Blum","year":"1989","unstructured":"Blum, L., Shub, M., Smale, S.: On a theory of computation and complexity over the real numbers: $$NP$$-completeness, recursive functions and universal machines. Bull. Am. Math. Soc. (New Series) 21(1), 1\u201346 (1989)","journal-title":"Bull. Am. Math. Soc. (New Series)"},{"key":"605_CR5","volume-title":"Real Algebraic Geometry","author":"J Bochnak","year":"2013","unstructured":"Bochnak, J., Coste, M., Roy, M.-F.: Real Algebraic Geometry, vol. 36. Springer, New York (2013)"},{"key":"605_CR6","unstructured":"Borcea, C.S.: Point configurations and Cayley-Menger varieties. Preprint, arXiv:math\/0207110 (2002)"},{"key":"605_CR7","doi-asserted-by":"publisher","unstructured":"Boutin, M., Kemper, G.: On reconstructing $$n$$-point configurations from the distribution of distances or areas. Adv. Appl. Math. 32(4), 709\u2013735 (2004). ISSN 0196-8858. https:\/\/doi.org\/10.1016\/S0196-8858(03)00101-5","DOI":"10.1016\/S0196-8858(03)00101-5"},{"issue":"1","key":"605_CR8","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1142\/S0218195907002239","volume":"17","author":"M Boutin","year":"2007","unstructured":"Boutin, M., Kemper, G.: Which point configurations are determined by the distribution of their pairwise distances? Int. J. Comput. Geom. Appl. 17(1), 31\u201343 (2007). https:\/\/doi.org\/10.1142\/S0218195907002239","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"605_CR9","doi-asserted-by":"publisher","unstructured":"Compagnoni, M., Notari, R., Ruggiu, A.A., Antonacci, F., Sarti, A.: The algebro-geometric study of range maps. J. Nonlinear Sci. 27(1), 99\u2013157 (2017). ISSN 0938-8974. https:\/\/doi.org\/10.1007\/s00332-016-9327-4","DOI":"10.1007\/s00332-016-9327-4"},{"key":"605_CR10","unstructured":"Dokmani\u0107, I.: Listening to distances and hearing shapes. Thesis, EPFL (2015)"},{"key":"605_CR11","doi-asserted-by":"crossref","unstructured":"Dokmani\u0107, I., Lu, Y.M., Vetterli, M.: Can one hear the shape of a room: the $$2$$-D polygonal case. In: 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp\u00a0321\u2013324. IEEE (2011)","DOI":"10.1109\/ICASSP.2011.5946405"},{"key":"605_CR12","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.dam.2015.10.029","volume":"204","author":"PM Duxbury","year":"2016","unstructured":"Duxbury, P.M., Granlund, L., Gujarathi, S., Juhas, P., Billinge, S.J.: The unassigned distance geometry problem. Discrete Appl. Math. 204, 117\u2013132 (2016)","journal-title":"Discrete Appl. Math."},{"issue":"225","key":"605_CR13","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1090\/S0025-5718-99-00995-3","volume":"68","author":"H Ferguson","year":"1999","unstructured":"Ferguson, H., Bailey, D., Arno, S.: Analysis of PSLQ, an integer relation finding algorithm. Math. Comput. Am. Math. Soc. 68(225), 351\u2013369 (1999)","journal-title":"Math. Comput. Am. Math. Soc."},{"key":"605_CR14","unstructured":"Gkioulekas, I., Gortler, S.J., Theran, L., Zickler, T.: Linear symmetries of the unsquared measurement variety. arXiv preprint arXiv:2007.12649 (2020)"},{"key":"605_CR15","doi-asserted-by":"publisher","unstructured":"Gortler, S.J., Thurston, D.P.: Generic global rigidity in complex and pseudo-Euclidean spaces. In :Rigidity and symmetry, Volume\u00a070 of Fields Inst. Commun, pp\u00a0131\u2013154. Springer, New York (2014). https:\/\/doi.org\/10.1007\/978-1-4939-0781-6_8","DOI":"10.1007\/978-1-4939-0781-6_8"},{"key":"605_CR16","doi-asserted-by":"crossref","unstructured":"Gortler, S.J., Theran, L., Thurston, D.P.: Generic unlabeled global rigidity. In: Forum of Mathematics, Sigma, Vol.\u00a07. Cambridge University Press, Cambridge (2019)","DOI":"10.1017\/fms.2019.16"},{"key":"605_CR17","volume-title":"Algebraic Geometry: A First Course","author":"J Harris","year":"2013","unstructured":"Harris, J.: Algebraic Geometry: A First Course, vol. 133. Springer, New York (2013)"},{"issue":"5","key":"605_CR18","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1137\/0218059","volume":"18","author":"J Hastad","year":"1989","unstructured":"Hastad, J., Just, B., Lagarias, J.C., Schnorr, C.-P.: Polynomial time algorithms for finding integer relations among real numbers. SIAM J. Comput. 18(5), 859\u2013881 (1989)","journal-title":"SIAM J. Comput."},{"issue":"7084","key":"605_CR19","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1038\/nature04556","volume":"440","author":"P Juh\u00e1s","year":"2006","unstructured":"Juh\u00e1s, P., Cherba, D., Duxbury, P., Punch, W., Billinge, S.: Ab initio determination of solid-state nanostructure. Nature 440(7084), 655\u2013658 (2006)","journal-title":"Nature"},{"key":"605_CR20","doi-asserted-by":"publisher","unstructured":"Laman, G.: On graphs and rigidity of plane skeletal structures. J. Eng. Math. 4, 331\u2013340 (1970). ISSN 0022-0833. https:\/\/doi.org\/10.1007\/BF01534980","DOI":"10.1007\/BF01534980"},{"issue":"1","key":"605_CR21","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1137\/120875909","volume":"56","author":"L Liberti","year":"2014","unstructured":"Liberti, L., Lavor, C., Maculan, N., Mucherino, A.: Euclidean distance geometry and applications. SIAM Rev. 56(1), 3\u201369 (2014). https:\/\/doi.org\/10.1137\/120875909","journal-title":"SIAM Rev."},{"issue":"18","key":"605_CR22","doi-asserted-by":"publisher","first-page":"6458","DOI":"10.3390\/app10186458","volume":"10","author":"JH Nam","year":"2020","unstructured":"Nam, J.H., Velten, A.: Super-resolution remote imaging using time encoded remote apertures. Appl. Sci. 10(18), 6458 (2020)","journal-title":"Appl. Sci."},{"key":"605_CR23","doi-asserted-by":"publisher","unstructured":"Owen, J.C., Power, S.C.: The non-solvability by radicals of generic 3-connected planar Laman graphs. Trans. Am. Math. Soc. 359(5), 2269\u20132303 (2007). ISSN 0002-9947. https:\/\/doi.org\/10.1090\/S0002-9947-06-04049-9","DOI":"10.1090\/S0002-9947-06-04049-9"},{"key":"605_CR24","doi-asserted-by":"crossref","unstructured":"Schoenberg, I.J.: Remarks to Maurice Frechet\u2019s Article\u201cSur La Definition Axiomatique D\u2019Une Classe D\u2019Espace Distances Vectoriellement Applicable Sur L\u2019Espace De Hilbert\u201d. Annals of Mathematics, pages 724\u2013732 (1935)","DOI":"10.2307\/1968654"},{"key":"605_CR25","doi-asserted-by":"publisher","unstructured":"Streinu, I., Theran, L.: Slider-pinning rigidity: a Maxwell-Laman-type theorem. Discrete Comput. Geom. 44(4), 812\u2013837 (2010). ISSN 0179-5376. https:\/\/doi.org\/10.1007\/s00454-010-9283-y","DOI":"10.1007\/s00454-010-9283-y"},{"key":"605_CR26","unstructured":"The Stacks Project Authors. Stacks Project (2018). http:\/\/stacks.math.columbia.edu"},{"key":"605_CR27","doi-asserted-by":"publisher","unstructured":"Whitney, H.: Elementary structure of real algebraic varieties. Ann. Math. (2), 66, 545\u2013556 (1957). ISSN 0003-486X. https:\/\/doi.org\/10.2307\/1969908","DOI":"10.2307\/1969908"},{"key":"605_CR28","doi-asserted-by":"publisher","unstructured":"Young, G., Householder, A.S.: Discussion of a set of points in terms of their mutual distances. Psychometrika 3(1), 19\u201322 (1938). ISSN 1860-0980. https:\/\/doi.org\/10.1007\/BF02287916","DOI":"10.1007\/BF02287916"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00605-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00605-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00605-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,3]],"date-time":"2024-02-03T23:03:42Z","timestamp":1707001422000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00605-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,25]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["605"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00605-x","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2023,11,25]]},"assertion":[{"value":"18 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 August 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 November 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}