{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:49:28Z","timestamp":1787320168902,"version":"build-2736575974"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[1991,11]]},"abstract":"<jats:p>Procedures for determining the feasibility of lower and upper bounds on Euclidean distances of fixed dimension play a central role in the analysis of many kinds of scientific data. Shown in this paper is how results from graph optimization theory can be used to solve the feasibility problem in one dimension, subject to the condition that the order of the points along the real line is known. The solution is used to derive a PSPACE, $O( n^{3}\\cdot n! )$-time sequential algorithm for finding one-dimensional representations subject to arbitrary distance (and order) constraints. The wider applicability of these results in measurement theory is discussed, in particular, Roy\u2019s elegant proofs of the classical representation theorems for interval orders and semiorders, and they are used to obtain a new representation theorem for a ternary relation called $\\varepsilon $-collinearity.<\/jats:p>","DOI":"10.1137\/0404047","type":"journal-article","created":{"date-parts":[[2005,2,23]],"date-time":"2005-02-23T08:03:04Z","timestamp":1109145784000},"page":"535-549","source":"Crossref","is-referenced-by-count":7,"title":["Bound Smoothing Under Chirality Constraints"],"prefix":"10.1137","volume":"4","author":[{"given":"Andreas W. M.","family":"Dress","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Timothy F.","family":"Havel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,8]]},"reference":[{"key":"R1","volume-title":"Theory and applications of distance geometry","author":"Blumenthal L.","year":"1953"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(86)80021-9"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0603058"},{"key":"R4","volume-title":"Distance geometry and molecular conformation","author":"Crippen G. M.","year":"1988"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0608005"},{"key":"R6","unstructured":"A. W. M. Dress, A. S. Dreiding, H. R. Haegi,  J.  Maruani, J.  Serre,  Classification of mobile molecules by category theory,  Symmetries and Properties of Nonrigid Molecules: A Comprehensive Survey, Studies in Physical and Theoretical Chemistry, Vol. 23, Elsevier Scientific, Amsterdam,  1983,  39\u201358"},{"key":"R7","unstructured":"A. W. M. Dress,  A.  Kerber,  Chriotopes and oriented matroids,  Diskrete Strukturen, algebraische Methoden und Anwendungen, Vol. 21, Bayreuther Math. Schriften,  1986 0681.05015"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(88)90009-1"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(89)90022-5"},{"key":"R10","volume-title":"The Art and Theory of Dynamic Programming","author":"Dreyfus S. E.","year":"1979"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.21236\/AD0708563"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90042-1"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(88)80005-1"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/S0092-8240(83)80020-2"},{"key":"R15","unstructured":"J. Heintz, P. Solern\u00f3, M.F. Roy,  G. X. Ritter,  On the complexity of semialgebraic sets,  Proc. Information Processing 89, Elsevier Science Publishers B.V., North-Holland,  1989,  293\u2013298"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(74)90001-5"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(71)90010-4"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093890809"},{"key":"R19","volume-title":"Measurement theory","author":"Roberts Fred S.","year":"1979"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-46550-5"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0165-4896(87)90005-9"},{"key":"R22","unstructured":"J. B. Saxe,  Embeddability of graphs in  k-space is strongly NP-hard,  Proc. 17th Allerton Conference in Communication, Control and Computing,  1979,  480\u2013489"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.2307\/2964389"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1525\/9780520348097"},{"key":"R25","unstructured":"Alfred Tarski,  What is elementary geometry?  The axiomatic method. With special reference to geometry and physics. Proceedings of an International Symposium held at the Univ. of Calif., Berkeley, Dec. 26, 1957-Jan. 4, 1958 (edited by L. Henkin, P. Suppes and A. Tarski), Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Co., Amsterdam,  1959,  16\u201329 21:49190092.38504"},{"key":"R26","volume-title":"Ten applications of graph theory","author":"Walther Hansjoachim","year":"1984"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0404047","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:55:17Z","timestamp":1787316917000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0404047"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,11]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1991,11]]}},"alternative-id":["10.1137\/0404047"],"URL":"https:\/\/doi.org\/10.1137\/0404047","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,11]]}}}