{"entities":{"Q1097038":{"pageid":1107790,"ns":120,"title":"Item:Q1097038","lastrevid":49128931,"modified":"2026-01-06T15:37:07Z","type":"item","id":"Q1097038","labels":{"en":{"language":"en","value":"Halfplanar range search in linear space and \\(O(n^{0.695})\\) query time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4033103"}},"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":"Q1097038$AD160A2F-890E-4CB2-A654-5DB9498BC1EC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bed7e27564829bc089e9d612a019949c607ab032","datavalue":{"value":{"text":"Halfplanar range search in linear space and \\(O(n^{0.695})\\) query time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1097038$D5E591D8-5FAA-4863-BFB0-2A76A31E42D3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"60c54aa94744ee2f1789860d6a9cd5b4b667a5a1","datavalue":{"value":"0634.68064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097038$F500794E-E879-4056-A5C8-8C5143EDC66A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2ef88219955ef05ae4f708f5ba4d79a98dcca50f","datavalue":{"value":"10.1016/0020-0190(86)90088-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097038$76DE2C75-1706-4ACC-A26F-B5A956737211","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097038$F8C62DA0-8AFB-4850-826B-582D336D6E25","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":"Q1097038$D0B01817-7134-48E5-A024-3CE74A4D7E58","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"87567820cafe89da06ac023d65530942da80515e","datavalue":{"value":"Let S denote a set of n points in the Euclidean plane. A halfplanar range query asks for the number of points in S which are contained in a given halfplane h. The authors introduce a data structure which stores S in O(n) space allowing an \\(O(n^{\\log_ 2(1+\\sqrt{5})-1})\\) query-time implementation of the above problem. The structure which they call conjugation tree, but in more recent work is often referred to as ham- sandwich tree, can be built in O(n log n) time. This tree structure can be seen as an improvement of Willard's polygon tree.    A line \\(\\ell\\) is a bisector of S if it partitions S into two sets P and Q which both contain at most n/2 points. Line \\(\\ell\\) is called a ham- sandwich cut of two sets P and Q if it bisects both of them. Such a cut always exists and the ham-sandwich tree T(S,\\(\\ell)\\) can now be roughly defined as follows. The root stores \\(\\ell\\) and the points in \\(S\\cap \\ell\\). Its two sons are the trees \\(T(P,\\ell_ 1)\\) and \\(T(Q,\\ell_ 1)\\), where \\(\\ell_ 1\\) is the ham-sandwich cut of sets P and Q, the partition of S by \\(\\ell\\). In splitting set S in four approximately equal parts within one ``level'', the ham-sandwich tree is, in a way, related to the well-known quad tree, although now, the separating lines are no longer necessarily axis-parallel.    After the definition of the tree structure, the authors state their algorithm for the halfplanar range query and give the \\(O(n^{0.695})\\) worst-case time analysis. Then they shortly address how results of Megiddo can be used to construct the tree in O(n log n) time. They end their paper by noting that ham-sandwich trees may be made dynamic using generic methods of Overmars and van Leeuwen.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097038$5D488A9A-F749-4A48-A499-A4448768EDE0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097038$64B30446-622C-427B-9D6B-C3B93D191CA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097038$1A6DA3BF-BB36-4E90-A33E-50CC48EEAE22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa4669cf5eaa224b5d3554d9705827ca09f43afb","datavalue":{"value":"52A37","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097038$C2401110-8041-42EF-98A7-572E57A7A80B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e2d3468aff90122a1abec5c40c453ed65c038547","datavalue":{"value":"4033103","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097038$83C51E9A-D20F-4D87-A83A-71084DC8C069","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097038$3A35B591-A624-4E4B-82F4-9244158EDC83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a4cbea57d6d29aa5a6d371e0843b973becac1a1","datavalue":{"value":"conjugation tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097038$EDA3960F-9A0E-45EA-89E0-A9D80C3E72A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2e87b0e2c2188084bac48f661378f8dc73d008e","datavalue":{"value":"ham-sandwich tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097038$613C1E05-5CA0-4B55-9D43-AF292212CF6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f42c01332c065b06b5a021518125d0a7e3bcf517","datavalue":{"value":"halfplanar range query","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097038$04D56C22-CBF4-49B0-BA52-A72AD42E4A59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d01f2d6a45429d9d4912e81d5382f3199c92225","datavalue":{"value":"worst-case time analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097038$66D96223-15DA-4BD6-9B39-7816EC0C35F8","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":"Q1097038$10183806-54E8-4D54-B297-B73782CD5C78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ebde143434d63bb91413660f73ab09b4563fd56f","datavalue":{"value":{"entity-type":"item","numeric-id":1262764,"id":"Q1262764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097038$DAEAD3DD-749C-4AF8-8009-0B389D2A5DC6","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":"Q1097038$BEEB4178-06A6-49CD-B3E3-9EBE7ED44D95","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6f37f9b7557ec518e2521cd5234f20a1c541a7bd","datavalue":{"value":"https://doi.org/10.1016/0020-0190(86)90088-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1097038$EDD00893-5628-4E97-95B0-5A97BF5C4649","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d68ba7f03d10818f5687c1f6a9b9526f2185ab9c","datavalue":{"value":"W2064098750","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097038$9A9F1D3B-2101-4382-A299-C8F8A287FA64","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1f677968f35d989276a14a982b8dce8819fb9d0c","datavalue":{"value":"Q54309897","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097038$0C62640F-DCD7-4FE4-A747-17DB630D235E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5eb040f4f53698848aa91aa2991b3af0b6cf962f","datavalue":{"value":{"entity-type":"item","numeric-id":4062679,"id":"Q4062679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097038$3EF831EB-6DD0-44A9-AFD3-93BC3CF6F2DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a876917bdf78b8c50d4a6a59c404fb7842a2db3e","datavalue":{"value":{"entity-type":"item","numeric-id":1165007,"id":"Q1165007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097038$16001531-A254-4B78-A791-6072408B2D84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da92b4d12846aa1606fa89a7ac5ca00163d7fc64","datavalue":{"value":{"entity-type":"item","numeric-id":4720805,"id":"Q4720805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097038$D99A42B9-3ABD-4B22-BDC8-1EC903ED6086","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4513c5833bc466d4a79387675503215f33e20eb0","datavalue":{"value":{"entity-type":"item","numeric-id":1394116,"id":"Q1394116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097038$14316C4C-EE69-4BEC-B5C8-AEEE8B11C2AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097038$A02255E7-90E9-4980-BA25-816A7DB365D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097038$A4FE62CE-68B5-46B7-8C81-51ADF6673310","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":"Q1097038$01BA642A-E288-4F4C-B16E-03882E40C807","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"900ec59125add65ef1a4c201cf6caf4bd0bcc622","datavalue":{"value":{"entity-type":"item","numeric-id":1152223,"id":"Q1152223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097038$2A757A16-3E68-4551-A86E-BA41B16C9BEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef00e0094b09cdff01d3eb0b0d934e3a15bc3263","datavalue":{"value":{"entity-type":"item","numeric-id":3313294,"id":"Q3313294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097038$F2E6725D-B3F8-4514-97F7-13ACD5A8EB87","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":"Q1097038$05794257-A19B-4F23-A703-24BF328FD683","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db8ec5290fbb1ca868ebef2e924821d821635f81","datavalue":{"value":{"entity-type":"item","numeric-id":685178,"id":"Q685178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"513ff5e9075e97ed8608e9e10e8328b281126c66","datavalue":{"value":{"amount":"+0.8123366832733154","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":"Q1097038$1B986A7B-C736-493B-BBBA-E1A9FCBF1C79","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":"bbec099d7960c8e4e5ef17d6ff86c86965cc5858","datavalue":{"value":{"amount":"+0.8120244741439819","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":"Q1097038$DC2893C3-CC01-4217-98A9-4493BD23EF53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25929a2d785b83d27fcadec94a12180579443d74","datavalue":{"value":{"entity-type":"item","numeric-id":1196295,"id":"Q1196295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e957167bb91251f6eefe845229788b61336706df","datavalue":{"value":{"amount":"+0.8109314441680908","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":"Q1097038$8ADB5F46-0F4C-43B5-BC35-0650755AABF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ef08ddba8d31265640915aae2cb4a9f02e2e8d5","datavalue":{"value":{"entity-type":"item","numeric-id":1199132,"id":"Q1199132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b6e19214d1b84296b2fdbe8f87cac09e7a3e95f","datavalue":{"value":{"amount":"+0.8098999261856079","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":"Q1097038$04B7AF6D-4B65-4736-8486-CBE417545E76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b370f09912f33ea954c53bd052c4c4268f0583e","datavalue":{"value":{"entity-type":"item","numeric-id":3358267,"id":"Q3358267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7cd7dabba89b839e0941720059ca9f690e1c20e2","datavalue":{"value":{"amount":"+0.8031154870986938","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":"Q1097038$DC7E71C2-3E60-4AA0-A65F-06496D63DFB9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1097038","badges":[]}}}}}