{"entities":{"Q685180":{"pageid":687029,"ns":120,"title":"Item:Q685180","lastrevid":63453105,"modified":"2026-04-11T13:16:11Z","type":"item","id":"Q685180","labels":{"en":{"language":"en","value":"Diameter, width, closest line pair, and parametric searching"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417113"}},"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":"Q685180$846B3BBE-E3C7-41C2-B046-3CBFDE7AB0C3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7f60179a0a85064e08fd1c6705fda3b839694f49","datavalue":{"value":{"text":"Diameter, width, closest line pair, and parametric searching","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685180$F0F6B786-B9BC-449B-9677-D7E572DFED63","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"801661e885592bc1c80d7d60fe6ed94297e68eaf","datavalue":{"value":"0777.68075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685180$98781213-5214-43DB-AD8C-3C629897E995","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fa697657dc8db2ee48f7f160b0a08a5a73049976","datavalue":{"value":"10.1007/BF02573973","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685180$856B0F8C-8CA3-4415-8C13-3457493D0A64","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a06f7d76e1dbfa89a80e5d40561052d9e137ca58","datavalue":{"value":{"entity-type":"item","numeric-id":242843,"id":"Q242843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$E65A285B-51AD-45A7-9F96-3B1D73B3E9EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"27055c7a0af767b1f36b14e7674bc0aa2224fdc0","datavalue":{"value":{"entity-type":"item","numeric-id":534491,"id":"Q534491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$F675D19C-1C05-49A7-9FFA-840591DC1961","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"05973d4747711a904c4eb354f325fda834906623","datavalue":{"value":{"entity-type":"item","numeric-id":396765,"id":"Q396765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$EA493388-3558-4DC7-A612-28D83D8678D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5ad91bd4a1378a015ef9d0cfb2ca621b16347f71","datavalue":{"value":{"entity-type":"item","numeric-id":525971,"id":"Q525971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$D2B3775B-5F86-4D0C-B445-2C829502E47B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$0B9A12DF-D65F-415A-AEF7-D8B69E64EF89","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"45eae072dc2fde41ae8741e47d8a8d06eb2b2f63","datavalue":{"value":{"time":"+1993-09-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685180$8FFD3AC7-C0AB-401A-9641-31C7F5839643","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dbddd170a1d94f970eb05b744a492daa01a56568","datavalue":{"value":"https://eudml.org/doc/131269","type":"string"},"datatype":"url"},"type":"statement","id":"Q685180$4E01BBA7-967A-48C2-A4FA-F6B4633BFEBA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c3b3ae0e264439c0856be41b9643d10149052dc7","datavalue":{"value":"We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved solutions for them. We obtain, for any fixed \\(\\varepsilon>0\\), an \\(O(n^{1+\\varepsilon})\\) algorithm for computing the diameter of a point set in 3-space, an \\(O(^{8/5+\\varepsilon})\\) algorithm for computing the width of such a set, and an \\(O(n^{8/5+\\varepsilon})\\) algorithm for computing the closest pair in a set of \\(n\\) lines in space. All these algorithms are deterministic.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685180$F475AC71-99E3-4335-A041-A270272C7009","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685180$779AF524-492F-40F7-A6BF-8BC08B21EC7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"52de7d4bf5a27d5ad252804eec58396bb3e40c44","datavalue":{"value":"90C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685180$AA1A912E-1AC8-4FEE-B2C7-B3CEBAD67CE5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0afe4f65ba9c578bedd6319b7ba11a091334aa54","datavalue":{"value":"417113","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685180$39C850F9-4637-4F64-B322-07B2BE50DCE7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6672c33ee6d787cced4fbaad14f2a43f562b88d2","datavalue":{"value":"parametric searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q685180$21158D69-BAA7-407A-AB97-7E1B14F724C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a2849fed3479edb812a736a871bd6b69ff9f050","datavalue":{"value":"geometric optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q685180$965EBB34-8759-45D6-A21B-AE409A207DF1","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":"Q685180$38F46F64-8C13-4018-9546-37668497DAD8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"855255da049552f9ac2b57b060dfb56946fc3319","datavalue":{"value":{"entity-type":"item","numeric-id":2366232,"id":"Q2366232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$1E5E06FA-28F1-4E26-A08D-4B6B140D7533","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb3ad06a850d903db617d4e20735c6d9d7e426c2","datavalue":{"value":{"entity-type":"item","numeric-id":1176318,"id":"Q1176318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$76699110-D666-49F4-8E6C-3F56BA51849E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"818b3710725f22f855a1a94def8326791b399279","datavalue":{"value":{"entity-type":"item","numeric-id":3141535,"id":"Q3141535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$0D6B722A-1E6A-4622-AFD2-D5DF2A0876A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33b1b0f3a36c1425b6de192e8a8db0881249dc17","datavalue":{"value":{"entity-type":"item","numeric-id":3138982,"id":"Q3138982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$8A4F4CF4-81FA-409F-B267-2BA6073962C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2b80375b1e77713b72b113eb93b23efd7566a72","datavalue":{"value":{"entity-type":"item","numeric-id":4763391,"id":"Q4763391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$E0D1C8E2-B2C4-4F92-8494-996C070ED773","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"454eeded42bf70a6f1be349b767065463fb1e843","datavalue":{"value":{"entity-type":"item","numeric-id":1209841,"id":"Q1209841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$3C69C930-2641-4174-88FA-5076B4F25614","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f74821186ca74ed67f096c47cf02e0914616796","datavalue":{"value":{"entity-type":"item","numeric-id":3481216,"id":"Q3481216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$B025E186-58C4-42A9-ACF6-DEFAAC42E7D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f54b4593646e5c58a76438875aa5358fab6ebdd","datavalue":{"value":{"entity-type":"item","numeric-id":1314429,"id":"Q1314429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$36719530-A1C8-45AF-B6D9-9B144DCD84C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1513e56781f8a82b707a1ecdbe4592e6abf75e4a","datavalue":{"value":{"entity-type":"item","numeric-id":3140430,"id":"Q3140430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$28F51614-230F-4663-882C-BF59797F3EF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8853722611c41579d02ebd114c164fbf2e1b547d","datavalue":{"value":{"entity-type":"item","numeric-id":1823685,"id":"Q1823685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$EE057351-6115-479B-BD7F-1F9BA277A88E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"735d640e7cc60fdab9cafbb506071ea3b381c8d7","datavalue":{"value":{"entity-type":"item","numeric-id":4601942,"id":"Q4601942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$8526773B-E926-4465-885F-8D69433B8C75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fda642304a10528bec663e87dda1b06a9086077","datavalue":{"value":{"entity-type":"item","numeric-id":3777473,"id":"Q3777473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$270BB433-DD13-434D-B32F-158D30AD3CC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e29b8e47936578f5cad24b50941e85f6a32ad9da","datavalue":{"value":{"entity-type":"item","numeric-id":3738618,"id":"Q3738618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$518FE939-F801-4E7B-86C3-1B8DC6DC8537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d50f8d7f7fb78d13d9136abf1be65711198cfd6","datavalue":{"value":{"entity-type":"item","numeric-id":1089803,"id":"Q1089803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$3C07C382-032F-43F0-82DF-FAF5891876EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"813773fa16a57d5ba1f1f634d7f3bafad0c0476d","datavalue":{"value":{"entity-type":"item","numeric-id":3967063,"id":"Q3967063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$FE654712-D0FE-4CF9-8FE0-68EE66EDBF04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb330b6b0bd526fcc8a653f5fe9578870e064bf2","datavalue":{"value":{"entity-type":"item","numeric-id":1182097,"id":"Q1182097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$922AFA14-A0B4-430B-B9F9-359898117E4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a80717a8b9fa13d127a2518180f24cd5aa9ae8f","datavalue":{"value":{"entity-type":"item","numeric-id":3359798,"id":"Q3359798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$F9CC02C5-559F-4B8D-88BD-8975AE30C124","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23ba82aea6b23a8be0d6632dd9615ef3f7361676","datavalue":{"value":{"entity-type":"item","numeric-id":4696650,"id":"Q4696650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$50C37FA3-0F3D-4F95-88DE-906187252D5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e424f1c4ff7c6f161b20d25abc72aff42c0b5cc","datavalue":{"value":{"entity-type":"item","numeric-id":3763585,"id":"Q3763585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$451E4081-7574-49D2-A45F-BBE35FF3BB06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecfa533020f36fda71fb4c8d7a937531d7fe4107","datavalue":{"value":{"entity-type":"item","numeric-id":4763428,"id":"Q4763428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$1D48DEDE-1870-4A5C-B472-9DD1AD3CB77E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"105a42b9d963cd1fb6e3de311b73c6eb9ace9be3","datavalue":{"value":{"entity-type":"item","numeric-id":4069777,"id":"Q4069777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685180$807E59D0-0823-4958-8BB8-7E88BDA0344B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0fa61f49bbcb4b1b607e6b12f4ca12318b447702","datavalue":{"value":{"entity-type":"item","numeric-id":4314492,"id":"Q4314492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"220c05c54327ff0ccda07a9ea010b8b3a6d42592","datavalue":{"value":{"amount":"+0.8215548992156982","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":"Q685180$D2DE31B6-24AF-40D3-A628-9458AE3E2B42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c382ef2d78434d44cbe04f086bb74032d98bb25","datavalue":{"value":{"entity-type":"item","numeric-id":4763391,"id":"Q4763391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8e3bf25f55bb55eb911037079d0c73b56289f39","datavalue":{"value":{"amount":"+0.8214184045791626","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":"Q685180$59522796-4D9C-4B10-8CFC-74C398722A93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c461274d0ccf5ae1639e78098f5a6988ad93593","datavalue":{"value":{"entity-type":"item","numeric-id":5946381,"id":"Q5946381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4415d0316cefb8fd9a34e3fb9cbb7ed549c8e846","datavalue":{"value":{"amount":"+0.7994610071182251","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":"Q685180$83B6A35C-E6C6-4720-8A88-E87B425DA17A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97c3965f9950a9fbc11b237544b0d14e0b840fd5","datavalue":{"value":{"entity-type":"item","numeric-id":3809267,"id":"Q3809267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4415d0316cefb8fd9a34e3fb9cbb7ed549c8e846","datavalue":{"value":{"amount":"+0.7994610071182251","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":"Q685180$28993F26-79A8-4A4A-8A1B-C27B97B4C31C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7dadfda7a506847bc85a63b948abde6f23b13837","datavalue":{"value":{"entity-type":"item","numeric-id":4250174,"id":"Q4250174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37be68118295abb8fee53ae93f40d48d9ba40220","datavalue":{"value":{"amount":"+0.7994462847709656","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":"Q685180$7C5DB3FE-9C4C-4AE5-997E-CF1080DCF2BC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Diameter, width, closest line pair, and parametric searching","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Diameter,_width,_closest_line_pair,_and_parametric_searching"}}}}}