{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:13:19Z","timestamp":1778497999587,"version":"3.51.4"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,12,1]],"date-time":"2015-12-01T00:00:00Z","timestamp":1448928000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2015,12]]},"abstract":"<jats:p>In this column, we consider natural problems in computational geometry that are polynomialtime equivalent to finding a real solution to a system of polynomial inequalities. Such problems are called \u21ffR-complete, and typically involve geometric graphs. We describe the foundations of those completeness proofs, in particular Mn\u00ebv's Universality Theorem, as well as some known \u21ffR-completeness results, and recent additions to the list. The results shed light on the complex structure of those problems, beyond mere NP-hardness.<\/jats:p>","DOI":"10.1145\/2852040.2852053","type":"journal-article","created":{"date-parts":[[2015,12,4]],"date-time":"2015-12-04T13:43:07Z","timestamp":1449236587000},"page":"69-78","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Computational Geometry Column 62"],"prefix":"10.1145","volume":"46","author":[{"given":"Jean","family":"Cardinal","sequence":"first","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles (ULB), Brussels, Belgium"}]}],"member":"320","published-online":{"date-parts":[[2015,12]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Dept. of Electrical Engineering and Computer Science","author":"Abbott Timothy G.","year":"2008","unstructured":"Timothy G. Abbott . Generalizations of Kempe's universality theorem. Master's thesis , Dept. of Electrical Engineering and Computer Science , Massachusetts Institute of Technology , 2008 . Timothy G. Abbott. Generalizations of Kempe's universality theorem. Master's thesis, Dept. of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 2008."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2881-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-015-9714-x"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-33099-2_14"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574701"},{"key":"e_1_2_1_6_1","volume-title":"Bernd Sturmfels, Neil White, and G\u00fcnter M. Ziegler. Oriented Matroids. Number 46 in Encyclopedia of Mathematics and its Applications","author":"Bj\u00f6rner Anders","year":"1999","unstructured":"Anders Bj\u00f6rner , Michel Las Vergnas , Bernd Sturmfels, Neil White, and G\u00fcnter M. Ziegler. Oriented Matroids. Number 46 in Encyclopedia of Mathematics and its Applications . Cambridge University Press , 2 nd edition, 1999 . Anders Bj\u00f6rner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and G\u00fcnter M. Ziegler. Oriented Matroids. Number 46 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2nd edition, 1999.","edition":"2"},{"key":"e_1_2_1_7_1","volume-title":"Simultaneous embedding of planar graphs. ArXiv e-prints","author":"Bl\u00e4sius Thomas","year":"2015","unstructured":"Thomas Bl\u00e4sius , Stephen G. Kobourov , and Ignaz Rutter . Simultaneous embedding of planar graphs. ArXiv e-prints , 2015 . Thomas Bl\u00e4sius, Stephen G. Kobourov, and Ignaz Rutter. Simultaneous embedding of planar graphs. ArXiv e-prints, 2015."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.2000.0482"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.05.006"},{"key":"e_1_2_1_10_1","unstructured":"Ulrich Brehm. A universality theorem for realization spaces of polyhedral maps. Special seminar on \"Universality of moduli spaces and geometry\" (06.11.2013) -- Hausdor Research Institute for Mathematics.  Ulrich Brehm. A universality theorem for realization spaces of polyhedral maps. Special seminar on \"Universality of moduli spaces and geometry\" (06.11.2013) -- Hausdor Research Institute for Mathematics."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62257"},{"key":"e_1_2_1_12_1","first-page":"171","volume-title":"Symposium on Computational Geometry (SoCG)","author":"Cardinal Jean","year":"2015","unstructured":"Jean Cardinal and Udo Hoffmann . Recognition and complexity of point visibility graphs . In Symposium on Computational Geometry (SoCG) , pages 171 -- 185 , 2015 . Jean Cardinal and Udo Hoffmann. Recognition and complexity of point visibility graphs. In Symposium on Computational Geometry (SoCG), pages 171--185, 2015."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00356"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035315.ch9"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(78)90039-4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2543581.2543589"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.10.042"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73046"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Branko Gr\u00fcnbaum. Convex Polytopes volume 221 (2nd ed.) of Graduate Texts in Mathematics. Springer-Verlag 2003.  Branko Gr\u00fcnbaum. Convex Polytopes volume 221 (2nd ed.) of Graduate Texts in Mathematics. Springer-Verlag 2003.","DOI":"10.1007\/978-1-4613-0019-9"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9394-8"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0040-9383(01)00034-9"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Donald E.\n      Knuth\n      . \n      Axioms\n       and \n      Hulls volume \n  606\n   of \n  Lecture Notes in Computer Science\n  . \n  Springer 1992\n  .  Donald E. Knuth. Axioms and Hulls volume 606 of Lecture Notes in Computer Science. Springer 1992.","DOI":"10.1007\/3-540-55611-7"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1071"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-010-9320-x"},{"key":"e_1_2_1_25_1","volume-title":"Intersection graphs of segments and 9R. ArXiv e-prints","author":"Matou\u0161ek Ji\u0159\u00ed","year":"2014","unstructured":"Ji\u0159\u00ed Matou\u0161ek . Intersection graphs of segments and 9R. ArXiv e-prints , 2014 . Ji\u0159\u00ed Matou\u0161ek. Intersection graphs of segments and 9R. ArXiv e-prints, 2014."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.09.004"},{"issue":"6","key":"e_1_2_1_27_1","first-page":"1312","article-title":"Varieties of combinatorial types of projective configurations and convex polyhedra","volume":"283","author":"Mn\u00ebv Nicolai E.","year":"1985","unstructured":"Nicolai E. Mn\u00ebv . Varieties of combinatorial types of projective configurations and convex polyhedra . Dokl. Akad. Nauk SSSR , 283 ( 6 ): 1312 -- 1314 , 1985 . Nicolai E. Mn\u00ebv. Varieties of combinatorial types of projective configurations and convex polyhedra. Dokl. Akad. Nauk SSSR, 283(6):1312--1314, 1985.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0082792"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/262839.262915"},{"key":"e_1_2_1_30_1","first-page":"211","volume-title":"Proceedings of the S\u00e9minaire Lotharingien de Combinatoire","author":"Richter-Gebert J\u00fcrgen","year":"1995","unstructured":"J\u00fcrgen Richter-Gebert . Mn\u00ebv's universality theorem revisited . In Proceedings of the S\u00e9minaire Lotharingien de Combinatoire , pages 211 -- 225 , 1995 . J\u00fcrgen Richter-Gebert. Mn\u00ebv's universality theorem revisited. In Proceedings of the S\u00e9minaire Lotharingien de Combinatoire, pages 211--225, 1995."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0093761"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.2307\/2118652"},{"key":"e_1_2_1_33_1","volume-title":"Point visibility graph recognition is NP-hard. ArXiv e-prints","author":"Roy Bodhayan","year":"2014","unstructured":"Bodhayan Roy . Point visibility graph recognition is NP-hard. ArXiv e-prints , 2014 . Bodhayan Roy. Point visibility graph recognition is NP-hard. ArXiv e-prints, 2014."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11805-0_32"},{"key":"e_1_2_1_35_1","volume-title":"Thirty Essays on Geometric Graph Theory","author":"Schaefer Marcus","year":"2012","unstructured":"Marcus Schaefer . Realizability of graphs and linkages . In Thirty Essays on Geometric Graph Theory . Springer , 2012 . Marcus Schaefer. Realizability of graphs and linkages. In Thirty Essays on Geometric Graph Theory. Springer, 2012."},{"key":"e_1_2_1_36_1","volume-title":"Nash equilibria, and the existential theory of the reals. manuscript","author":"Schaefer Marcus","year":"2011","unstructured":"Marcus Schaefer and Daniel \u0160tefankovi\u010d . Fixed points , Nash equilibria, and the existential theory of the reals. manuscript , 2011 . Marcus Schaefer and Daniel \u0160tefankovi\u010d. Fixed points, Nash equilibria, and the existential theory of the reals. manuscript, 2011."},{"key":"e_1_2_1_37_1","volume-title":"Stretchability of pseudolines is NP-hard. Applied Geometry and Discrete Mathematics{The Victor Klee Festschrift, 4:531--554","author":"Shor Peter W.","year":"1991","unstructured":"Peter W. Shor . Stretchability of pseudolines is NP-hard. Applied Geometry and Discrete Mathematics{The Victor Klee Festschrift, 4:531--554 , 1991 . Peter W. Shor. Stretchability of pseudolines is NP-hard. Applied Geometry and Discrete Mathematics{The Victor Klee Festschrift, 4:531--554, 1991."},{"key":"e_1_2_1_38_1","volume-title":"N\u00fcrnberg F. Korn","author":"Christian Staudt Karl Georg","year":"1847","unstructured":"Karl Georg Christian Staudt . Geometrie der Lage . N\u00fcrnberg F. Korn , 1847 . Karl Georg Christian Staudt. Geometrie der Lage. N\u00fcrnberg F. Korn, 1847."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.12.003"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2852040.2852053","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2852040.2852053","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:17Z","timestamp":1750222457000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2852040.2852053"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["10.1145\/2852040.2852053"],"URL":"https:\/\/doi.org\/10.1145\/2852040.2852053","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2015,12]]},"assertion":[{"value":"2015-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}