{"entities":{"Q1079817":{"pageid":1090569,"ns":120,"title":"Item:Q1079817","lastrevid":69913350,"modified":"2026-04-13T11:10:46Z","type":"item","id":"Q1079817","labels":{"en":{"language":"en","value":"Computing circular separability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3964871"}},"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":"Q1079817$EAE2BF1D-2CBE-497B-B0D6-389737CADE4B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2b721b047d9abddff3ae62bdc42ed7bb1e18004c","datavalue":{"value":{"text":"Computing circular separability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1079817$F6321E7E-F087-4CF4-8C8D-B4A02950FF68","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6afa9e2dc5568eac8bd47177cdfc43d2bd6de6e3","datavalue":{"value":"0598.52008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079817$31BB7C6F-F70F-40E5-82F0-3C6360267DD9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4bd3b4d8d88b6cfb96453598c41de29283a758e9","datavalue":{"value":"10.1007/BF02187688","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079817$6867E199-C3D9-4BCD-A161-4E016BBCA1D7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"931993058e8741daaf0799b9497e3ca481154652","datavalue":{"value":{"entity-type":"item","numeric-id":223096,"id":"Q223096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079817$7E33DC0F-A473-4F72-97E2-A01E15F0802A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"be690050f94666bf6766a43de05350885a6401a1","datavalue":{"value":{"entity-type":"item","numeric-id":613423,"id":"Q613423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079817$709F6950-B5F4-4FF9-AC2E-D221A4F38457","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"97ae1d05248d2d268c19d2f23763f39d29e49e68","datavalue":{"value":{"entity-type":"item","numeric-id":916386,"id":"Q916386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079817$96EBBBF1-2D89-4BA6-B0EF-62DAFD8A9F3E","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":"Q1079817$2C051635-7C91-4066-8C87-70E9B4FD3A2D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1079817$7D069D57-556A-4BCA-81C5-59A4BEBC0E8B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8814ead5f2b83b1574e09f4bbbe5b41ca8095cdf","datavalue":{"value":"https://eudml.org/doc/130985","type":"string"},"datatype":"url"},"type":"statement","id":"Q1079817$373E205F-29E3-4853-AF07-5642A93545E6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"11ca1c0053d06d24ff8b662e128a15f248cd5a7d","datavalue":{"value":"Let \\(S_ 1\\) and \\(S_ 2\\) be two sets of points in \\(R^ 2\\) with \\(| S_ 1| +| S_ 2| =n\\). \\(S_ 1\\) and \\(S_ 2\\) are said to be circularly separable if there is a circle C such that each point of \\(S_ 1\\) is interior to or on the boundary of C while each point of \\(S_ 2\\) is exterior to or on the boundary of C. The results of this paper consist of: 1) deciding whether two sets \\(S_ 1\\) and \\(S_ 2\\) are circularly separable and showing that this decision can be achieved with the speed O(n); 2) finding a smallest separating circle and showing that it can be found in O(n) time; 3) finding all largest separating circles and showing that this can be accomplished in O(n log n) time. It is also proved that these results are optimal.    These problems can be extended to spherical separability in higher dimensions. The authors derive the corresponding results.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079817$11BD0F20-ECA7-48CA-BCED-E8DE2964024E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"145b3547074abae69f7ea12a847bac9f122cc911","datavalue":{"value":"52A40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079817$FBB9F742-D76B-499C-B47C-6F79EA41E3C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079817$52DFD094-E8D0-4DDC-B895-FDF0CCBAF4F0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4c387723b59efe8645904c35954e7d9e73a9ab82","datavalue":{"value":"3964871","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079817$F6CA4759-4541-4B29-B65E-DA3C452471D2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1050af34164b242373351b3866875373665006db","datavalue":{"value":"circular separability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079817$80B616C1-6CE2-4A2B-8F03-31A905C120A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a08efa1a08a750d06fca0196004a17a02a35c592","datavalue":{"value":"linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079817$CCB29EAE-D392-4A44-A431-02504CC12F8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d2a942004e7c3ebf174ed889f18fd8e1f8b9b24b","datavalue":{"value":"Voronoi diagrams","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079817$63748FB0-5647-4092-B60B-8675334E1967","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079817$300624FD-5F77-42ED-8F09-F1868D493D7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"421f625bcc5b9818ffad87eb92a5a4410ef861b6","datavalue":{"value":"spherical separability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079817$747B7CB5-15E0-4DC6-A964-41093D577A3D","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":"Q1079817$5AB253AF-9203-47D2-B490-DEE1B7F3C8A1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7665c1640a9da2eb8d01a5539680d51d13fa3a15","datavalue":{"value":{"entity-type":"item","numeric-id":3315272,"id":"Q3315272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079817$916D93A6-38B1-490C-86A3-C168833E234D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bf064dae3c139752fca50ce0febcfc2237c8808","datavalue":{"value":{"entity-type":"item","numeric-id":759483,"id":"Q759483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079817$FF3BF727-D5F8-4C91-B2D1-28FD46A9064A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"429c35569b8a5a0b924cd4d83b58957d9f289377","datavalue":{"value":{"entity-type":"item","numeric-id":5904560,"id":"Q5904560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079817$21993A2E-C4DA-4813-9D2A-00CC07C0236F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0fb4c1f0357b435cf9416a32bf1ccc674d1145c","datavalue":{"value":{"entity-type":"item","numeric-id":1069424,"id":"Q1069424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079817$36CC9B37-F732-4FEA-916C-19DD237FD628","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"750f6d16c6420fa29e521e2e84425ccb3c1aedc5","datavalue":{"value":{"entity-type":"item","numeric-id":1079823,"id":"Q1079823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079817$D28481B6-D255-4666-8A90-2F42D4C21853","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":"Q1079817$D5533D81-F79D-4F4C-A095-85946753C64D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a9e941b224ae72629b3e2cd083153eeebdfa379","datavalue":{"value":{"entity-type":"item","numeric-id":3670553,"id":"Q3670553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079817$8AB57FBA-6050-4C98-87D4-098665D6F3FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f837c623bf58c21b7997511c468a133c0deb27a9","datavalue":{"value":{"entity-type":"item","numeric-id":3778541,"id":"Q3778541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079817$D65E1CC0-21E3-4812-81FA-276078488529","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f62acb5eac89db2e3c6032dabab2d88e9279dd27","datavalue":{"value":{"entity-type":"item","numeric-id":4110607,"id":"Q4110607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079817$97C6F4F9-BDE7-4F98-A3B4-0F4B71D07ADB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"859815f7fbf6618b8f5feb7326a14b63dfee2464","datavalue":{"value":{"entity-type":"item","numeric-id":3039008,"id":"Q3039008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079817$7DE1C150-6AE5-4099-8CEC-E52F86F94718","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f9da3a1940db7207ee0d7a21679a8d607486dd34","datavalue":{"value":"W2130596403","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079817$361DBBF0-E180-4B91-8E29-3D9049C78355","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88c3d1d9780e7be749b620ef0513ee087c4ad30e","datavalue":{"value":{"entity-type":"item","numeric-id":3796753,"id":"Q3796753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"906f1f1e60e00c7b64fb105ee34f921dd3af6148","datavalue":{"value":{"amount":"+0.9459194540977478","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":"Q1079817$3AEF95A2-FCEC-42F3-A086-DD046C078984","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7adaaaca25dd7c2a32697df3b520d5ebc8135c1d","datavalue":{"value":{"entity-type":"item","numeric-id":5943827,"id":"Q5943827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78d6a2cfdbc22e4ccdd250855563f4be81ca84ec","datavalue":{"value":{"amount":"+0.8914249539375305","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":"Q1079817$EE5E0B8B-42E5-4F5C-9D70-5CF2EE1E02B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbb438ef64e621bf1c1998ca63781ed49ff0be51","datavalue":{"value":{"entity-type":"item","numeric-id":4682203,"id":"Q4682203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5cdea29fc7ab430cc33d5eeffafd123744067347","datavalue":{"value":{"amount":"+0.8498698472976685","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":"Q1079817$C53A430C-ED39-4029-B730-4790272F92D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"684a133455b9d1f54601254b76acb075e3d58e99","datavalue":{"value":{"entity-type":"item","numeric-id":387873,"id":"Q387873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca455178e432d102ac34e0ec1e4d0c93bd846a9e","datavalue":{"value":{"amount":"+0.8301284909248352","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":"Q1079817$C9AA048A-7921-41AC-B36C-971B0B5C1C88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f75a24302b58e389b87ed2bc55bc2195e542ec0","datavalue":{"value":{"entity-type":"item","numeric-id":4028120,"id":"Q4028120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07d2b9447e27b0d6520667f6dd6595c22d9d4ded","datavalue":{"value":{"amount":"+0.8149129152297974","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":"Q1079817$6CBE6C38-07DE-4752-A596-1ABEFE55C25B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computing circular separability","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computing_circular_separability"}}}}}