{"entities":{"Q1091824":{"pageid":1102576,"ns":120,"title":"Item:Q1091824","lastrevid":49081630,"modified":"2026-01-06T13:54:47Z","type":"item","id":"Q1091824","labels":{"en":{"language":"en","value":"Computing a ham-sandwich cut in two dimensions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4011949"}},"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":"Q1091824$08C7ED83-8A82-4B80-A756-1216E9BAA752","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e3c43d695c1b1b58dbf07e375ff4bbeb74776a8f","datavalue":{"value":{"text":"Computing a ham-sandwich cut in two dimensions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1091824$DBCCA7F8-78D6-473A-BDE8-7A25F0A2BD55","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3fb3debc3d8801c3e7a0698a885ff97a809405a7","datavalue":{"value":"0623.68058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091824$605AFD85-B4A5-420C-91DE-F9F2A703C12B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fee3573d5fcf1461752385a8417257b391a94a28","datavalue":{"value":"10.1016/S0747-7171(86)80020-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091824$3A9F1791-F198-4C58-B514-D571963DBEDF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea72303f92787da89554ee5fa15621068821a762","datavalue":{"value":{"entity-type":"item","numeric-id":99061,"id":"Q99061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091824$A69ABCD1-638C-4BF1-B7DB-6AC9D5437367","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":"Q1091824$9C119C09-DA87-44C0-AFC6-B672CB10A7AC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b6615523a19007af4135180e2fa47b72bd460d73","datavalue":{"value":"According to the ham-sandwich theorem, for any two finite point sets in the plane there is a line that bisects both sets. Here we say that a line bisects a point set if at most half of the points lie in any open half- plane determined by the line. Lines that simultaneously bisect two point- sets have application to various geometric problems including range search in the plane.    If the two (finite) point sets are separated (that is, their convex hulls are disjoint), then a line that bisects both sets can be found in O(n) time where n is the total number of points. A considerably more complicated algorithm involving e.g. a parallel sorting scheme can find such a line in O(n log n) time if the point sets are not separated. This paper extends the linear algorithm due to Megiddo to the case of non- separated sets and obtains an algorithm that runs in \\(O((n_ 1+n_ 2) \\log (\\min \\{n_ 1,n_ 2\\}+1))\\) time. The advantages of this algorithm over the O(n log n) scheme is that it is significantly simpler and that it is faster if \\(n_ 1\\) and \\(n_ 2\\), the cardinalities of the two sets, are very unbalanced. It is open whether or not linear time is sufficient to find a simultaneous bisector in the non-separate case.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091824$F8BF80E8-25ED-4200-8BEF-DC95C12067D3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091824$EE3E43FB-77F1-47BB-87C2-525CBFB81DD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cfff2e3b7f009b69ae82e4aa296ae1902bd02ff","datavalue":{"value":"68Q60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091824$4DC66BDB-DC24-4696-8209-DA4633959D31","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f12c1f18d3d1e6a23846d89afbc99e8781c4aa82","datavalue":{"value":"4011949","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091824$FEE962F5-BA5B-493C-AF6E-104A03980282","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091824$6DB9D5C4-6BE8-48F8-A095-055C09D14F8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"30684462670762b9964ab14059bdcd92ad083032","datavalue":{"value":"prune-and-search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091824$C1943CA0-6562-494E-8A5E-C325F6F94F96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a06cd36228dc11cb835e94732c65e8dbb873733","datavalue":{"value":"geometric transforms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091824$1F7445A4-10A5-4D61-B499-91ECF989D05D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"deb4462ca86e528786a931d83502107c22078a6f","datavalue":{"value":"ham- sandwich theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091824$7997D45B-D581-4330-B569-A2E184CC6E69","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"00d02143912031e9be5ddac2dd266c2f20dbde7a","datavalue":{"value":"Q56428476","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091824$8DA1BFF0-E3CD-46AD-8FF9-405F577C4492","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":"Q1091824$686B516F-1EAD-47E7-8F17-E6C2FD45EC5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"843e2bec8c1f564bd32dfb82036d1b6eec2d96a6","datavalue":{"value":{"entity-type":"item","numeric-id":2482892,"id":"Q2482892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091824$A4F2AFEB-8F65-4E53-BBAC-E916CE508A31","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":"Q1091824$8787E604-1695-4438-B9F4-C883DC75B69C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d656ee44a323e749d5c6d4cf3e4b8271c3af114","datavalue":{"value":{"entity-type":"item","numeric-id":2542990,"id":"Q2542990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091824$958CE102-0F43-42A9-96BD-A874767509AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cab9d45eabd7810931553fb2ae7e45ddb17078a1","datavalue":{"value":{"entity-type":"item","numeric-id":1091825,"id":"Q1091825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091824$FD99C387-9C3F-426D-98DB-26CCA13F8817","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f90fabbf9c7230e3d7148f357dd20ca8025b63e","datavalue":{"value":{"entity-type":"item","numeric-id":3704524,"id":"Q3704524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091824$99248E45-485C-4CBA-80A6-4268C18EFD0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50eda2043c94a0a2b9f4b5d31dd4f5e608303363","datavalue":{"value":{"entity-type":"item","numeric-id":3936209,"id":"Q3936209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091824$5077ED95-8A02-4B7C-944F-CB3A8290878D","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"4e52babd21f9de7652737f2a07df7c8df1183739","datavalue":{"value":"journals/jsc/EdelsbrunnerW86","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091824$EF7CC832-4C2D-4757-A5D7-34442FF222C4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91a8c2969b261af1073771706c6aa54c28401337","datavalue":{"value":{"entity-type":"item","numeric-id":1329191,"id":"Q1329191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ae3aa823708c4fcb858ddbf78eb32d14b8a5758","datavalue":{"value":{"amount":"+0.927251160144806","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":"Q1091824$EDD2D384-4B6D-4BBE-A1FD-473F8DD83E6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f94d7281cc02661a52f62f3310e9e72f75bb99c","datavalue":{"value":{"entity-type":"item","numeric-id":3817605,"id":"Q3817605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15f48414b031a2f98e1a1048646934a19518c737","datavalue":{"value":{"amount":"+0.921286165714264","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":"Q1091824$14FE5D8B-282A-413B-B2B4-BAF267DCA79F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03fe62179460a9481c3905cc49ba964642c96658","datavalue":{"value":{"entity-type":"item","numeric-id":1025301,"id":"Q1025301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2858d94dc2c71d5caf945204d69f24ceac6a4d16","datavalue":{"value":{"amount":"+0.9101471304893494","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":"Q1091824$5C4A505D-81DA-4586-BAD1-F6593A87DAAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcf9ee30a3c86374bdf2ce93a89d4c7797af5a70","datavalue":{"value":{"entity-type":"item","numeric-id":2373932,"id":"Q2373932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b810ca54b8ea18cecee08da7b54bc6f92a3bad3","datavalue":{"value":{"amount":"+0.8780773878097534","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":"Q1091824$E8A20447-D374-4518-98FF-4FC36F4D3220","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3f9f5e545167a792d25a0bc82a51c3fb4c29c4a","datavalue":{"value":{"entity-type":"item","numeric-id":1178190,"id":"Q1178190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"356737b5e916e1ace657d08f54cb0fd3aa3f78d2","datavalue":{"value":{"amount":"+0.8775781989097595","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":"Q1091824$898BF835-0C40-44C6-9938-82BD7BD617AF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1091824","badges":[]}}}}}