{"entities":{"Q419363":{"pageid":421130,"ns":120,"title":"Item:Q419363","lastrevid":51470756,"modified":"2026-01-18T10:00:50Z","type":"item","id":"Q419363","labels":{"en":{"language":"en","value":"On a class of \\(O(n^2)\\) problems in computational geometry"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6036375"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419363$B683AA3F-73F5-4E00-A43E-1BBA482739E8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e9bd12f71b092a1f3ac21d1e7aac2c8ea41596e5","datavalue":{"value":{"text":"On a class of \\(O(n^2)\\) problems in computational geometry","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q419363$D7BB4927-2BA1-4102-9088-F590D058B060","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"eadd12d5a39ea732e4dc36b38acd098aa0496ca2","datavalue":{"value":"1254.68301","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q419363$6D8F606E-67F8-46DE-A42D-E901DB31603E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f4e503b2c2fe6b93946ce3902b47e8ed664f42bf","datavalue":{"value":{"entity-type":"item","numeric-id":419361,"id":"Q419361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419363$16B956B9-6580-4D6A-87C4-9DE554A91EA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3f813421ca1324eea7267dc8879260a77170dbb2","datavalue":{"value":{"entity-type":"item","numeric-id":419362,"id":"Q419362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419363$A4BC40B0-430F-4C51-97E1-A298241A2C92","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419363$24770312-4A30-4188-8D8C-C316E0CE99FD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cce433cdcb3478d8106ca3fd120344ac0deb7f83","datavalue":{"value":{"time":"+2012-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q419363$55738A73-F7D5-4417-8E01-D4AB58B132BF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1cd2b6dd68fecdb36ab86b80c724d1a41bdf5869","datavalue":{"value":"To honor the winners of their 2011 Test-of-time award, the Computational Geometry journal has reprinted this 1995 article, in which the \\textsc{3sum} problem is related to a diverse collection of other geometric computational problems. The \\textsc{3sum} problem asks one to determine if, given a set of \\(n\\) integers, there are three integers from this set whose sum is zero. This problem is known to have a solution that runs in \\(\\Theta(n^2)\\) time in the worst case, but it is not known if a faster solution exists. The authors define a problem \\textsc{Pr} to be \\textsc{3sum}-hard if \\textsc{3sum} can be solved using \\textsc{Pr} a constant number of times, plus an additional \\(o(n^2)\\) amount of time. It is shown that many problems are in fact \\textsc{3sum} hard. Some incidence problems are \\textsc{3sum}-hard, such as determining if there is a line that contains at least three points from among a collection of \\(n\\) points in the plane. There are separation problems that are also \\textsc{3sum} hard, such as determining if there is non-horizontal line that does not intersect a given set of \\(n\\) (possibly half-infinite) horizontal line segments. Some covering problems also fit into this category. For instance, determining if the union of a set of \\(n\\) rectangular strips in the plane completely cover a given axis-aligned rectangle is \\textsc{3sum}-hard. The authors show that there are visibility and motion problems that are also \\textsc{3sum}-hard. The article is largely self-contained and accessible to a general audience familiar with computational geometry.","type":"string"},"datatype":"string"},"type":"statement","id":"Q419363$0CB3A2AC-CEAE-4A35-A2F5-A6E5D9C8C2AF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c9684a93e5f98988685744c9cbf253435c411cf8","datavalue":{"value":{"entity-type":"item","numeric-id":510384,"id":"Q510384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419363$12EC246F-8390-4C20-85F6-0B5140028E01","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q419363$57E27787-BA56-49A0-91E0-CE6B5D9A6435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q419363$36B61874-DB1D-4524-9194-945350EF40DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q419363$72BEF658-5D02-421E-8BB9-FCFEEA0CA46C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"423f40853bda96979df8ff41c25bff1254d3f621","datavalue":{"value":"6036375","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q419363$008FFFA6-EC3A-4171-8DFA-540A746599EB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c08c9b4654a52a6004bed30631d3322d8db685e1","datavalue":{"value":"incidence","type":"string"},"datatype":"string"},"type":"statement","id":"Q419363$A7F0E5EA-257E-4459-977D-9E71003F115B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16382045e0cfe30182ad180ef8d44f60dac5e0df","datavalue":{"value":"separator","type":"string"},"datatype":"string"},"type":"statement","id":"Q419363$9EEA76A3-0436-4424-ABFF-6CD9768FA174","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21d142027bf3153eebb876131ac5297907f4e838","datavalue":{"value":"covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q419363$E9B362B1-E2CA-405E-A9A0-DE7846770375","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7bfd605e8d1eec2e403cfe1b9f8fb6385b43b4a0","datavalue":{"value":"visibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q419363$D3003CEA-7586-47E5-B344-364B4987B273","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f3c4174a5d716f293c7527ce1cefdfb920908bc","datavalue":{"value":"motion planning","type":"string"},"datatype":"string"},"type":"statement","id":"Q419363$2AD297F3-A95B-475D-9B69-520C22CE7F1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3fd91ba874b7001e4212309b6624b41616033f02","datavalue":{"value":"3sum-hard problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q419363$9C3A5D33-D973-4C8D-83AC-2C2A9598C303","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419363$76ABE449-A5A9-452E-A5DA-F65680475F05","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a382c6766862b5ae00fbad11dfc028adc5a6a0cd","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2011.11.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q419363$8782A822-240D-46DB-B68B-F9DBBCDF92B7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"43e00051c0b04ba659ae91b57facddad6920cb72","datavalue":{"value":"W2150123893","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q419363$332E37E2-3EE3-45DF-8D1F-863674954287","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"21d3b5a6f2434ce563cad459d53773ab72bb0f43","datavalue":{"value":{"entity-type":"item","numeric-id":1401872,"id":"Q1401872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419363$5026D7A9-472C-4D33-81A8-7F5D8B9A4B24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1527977d1e97f551ee80e9595c567d4fb5b3ce20","datavalue":{"value":{"entity-type":"item","numeric-id":1176324,"id":"Q1176324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419363$E2BF8EEB-99EF-4081-9D04-C6BCBCCC5A28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25b026e498c7466f890693e678f90760ff4b1c4e","datavalue":{"value":{"entity-type":"item","numeric-id":3772828,"id":"Q3772828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419363$C3569A08-DA76-4A08-8A79-1EFB13C7D323","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d51e66379b70ceed54487a727ee6745d725b0e35","datavalue":{"value":{"entity-type":"item","numeric-id":1122981,"id":"Q1122981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419363$DE35090F-D19E-417B-9953-B73C65B92D15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba1eef9a8de19b57864dc87d5c058554f9d6c7cf","datavalue":{"value":{"entity-type":"item","numeric-id":582900,"id":"Q582900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419363$E41EC8CC-9177-4557-A9D5-09BDED28DBF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cfbea157a219f384089d047adf4b99305837f08","datavalue":{"value":{"entity-type":"item","numeric-id":1314526,"id":"Q1314526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419363$0D87592F-D4D9-4CAB-A614-89EA9185E983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf41f453f62505ef8d0891b560c167368ddeaa03","datavalue":{"value":{"entity-type":"item","numeric-id":1346125,"id":"Q1346125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419363$D2B9D3F2-DD12-430D-90EF-C752EBDC37B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0b2d77efe01890b2cef4fd0c4157d026bd2bd17","datavalue":{"value":{"entity-type":"item","numeric-id":4286234,"id":"Q4286234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419363$F46AD275-0BBF-4D9B-B4DC-95FED65B3956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694910451200ab7067ebbccacf142af3ac2a2369","datavalue":{"value":{"entity-type":"item","numeric-id":3992847,"id":"Q3992847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419363$4D0C727C-4C26-4500-905D-8A3AEC367FFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9bbf22b6158e8d9d2bfc0362965dd434337c2cca","datavalue":{"value":{"entity-type":"item","numeric-id":1314536,"id":"Q1314536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419363$B46256D6-D63F-4578-B16D-ED1173D75A10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09ef5c4f98018d9423ccf8fc456f7581591ca53e","datavalue":{"value":{"entity-type":"item","numeric-id":5056095,"id":"Q5056095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419363$5170BFC1-4F33-46B3-A4E8-90ABE92B6DD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ffec4d94b7b012095f39126ed96f3bf822347da","datavalue":{"value":{"entity-type":"item","numeric-id":1062764,"id":"Q1062764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419363$1324CA6D-AB43-4474-85B9-11EEAD485D39","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d921dd4259af11ae78cc52f923a3d26b6e9c1c7a","datavalue":{"value":"10.1016/J.COMGEO.2011.11.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q419363$2B518E9D-C08E-40D2-9855-F55269A597FC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"697933032cbb2da736f0ad1d5b015199ca679e59","datavalue":{"value":{"entity-type":"item","numeric-id":1903639,"id":"Q1903639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26941a5e701ea22bcee5324d7bff5bcb9d1a6a21","datavalue":{"value":{"amount":"+0.8596435785293579","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q419363$93DBABAA-F4E3-44ED-8AD6-C467AF340F05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90123b73be63a89fc8f1eeb48377722bce38a22a","datavalue":{"value":{"entity-type":"item","numeric-id":4252379,"id":"Q4252379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d997b3c93422301b147bbc223bcb758c8df29a39","datavalue":{"value":{"amount":"+0.8199664950370789","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q419363$5660C709-AC71-4673-B48E-1DCAB98DCB26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f636582db20523a1b37e42a8b6e3b436c16c9271","datavalue":{"value":{"entity-type":"item","numeric-id":4682166,"id":"Q4682166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c80a29272bea1dfe66db93d169b245f2c6e8d4cf","datavalue":{"value":{"amount":"+0.7730104327201843","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q419363$DDB46F12-5639-4DBD-AC41-074DB0E72AAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"053cf48e8d1367250df4dd078b54648f1cb02d6d","datavalue":{"value":{"entity-type":"item","numeric-id":4973055,"id":"Q4973055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46a110ccdd0d1bd928a49ac4703b7438d94ca045","datavalue":{"value":{"amount":"+0.7728782892227173","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q419363$7CC73551-4203-4256-8D24-36D8C9825E00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43c6258d8941ea0aecac54be47c64563c1b451ad","datavalue":{"value":{"entity-type":"item","numeric-id":2105319,"id":"Q2105319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76e48b33fec161ea649402acb4a98d8c042b8e41","datavalue":{"value":{"amount":"+0.7318487167358398","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q419363$5E69E039-57BD-49E5-AE20-E23C2DB5E5E0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:419363","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:419363"}}}}}