{"entities":{"Q1077166":{"pageid":1087918,"ns":120,"title":"Item:Q1077166","lastrevid":48945148,"modified":"2026-01-06T06:51:11Z","type":"item","id":"Q1077166","labels":{"en":{"language":"en","value":"Halfspace range search: An algorithmic application of k-sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3956453"}},"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":"Q1077166$376E845C-A606-459B-97B1-FD244155B269","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0213a50cc0b389c117072719b3e75f184515747e","datavalue":{"value":{"text":"Halfspace range search: An algorithmic application of k-sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1077166$7FF8012D-5E47-407A-BFA5-E028324B6007","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d17b5f218a08cccb0f1f16810acf5fce775381a7","datavalue":{"value":"0594.68055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077166$A964A0CD-2C10-4715-AE0A-236FFEB4F91F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"163d6748029038c25e22b91229710c0a367537fa","datavalue":{"value":"10.1007/BF02187685","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077166$DA441416-638B-40EE-87A6-D3599864391F","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":"Q1077166$89F7F9A7-3B49-496C-AB29-1718166F461C","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":"Q1077166$38BE580D-31D7-4214-A51B-8351E9EE7DDB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c4df0fd60104c5bac4d86bdebb76430b671d5e86","datavalue":{"value":"https://eudml.org/doc/130983","type":"string"},"datatype":"url"},"type":"statement","id":"Q1077166$6CB46488-CE35-4126-B3D9-4CEAD698EA78","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3307cb9bc02d04eb8d3f55256e3977671e900167","datavalue":{"value":"Given a fixed set \\(S_ n\\) of n points in Euclidean space \\(E^ 3\\) and a query plane \\(\\pi\\), the halfspace range search problem asks for the retrieval of all points of \\(S_ n\\) on a chosen side of \\(\\pi\\). The authors prove as main results: (1) the total number of j-sets of \\(S_ n\\) \\((=subsets\\) of \\(S_ n\\) of size j which can be separated from the rest of \\(S_ n\\) by a plane), \\(j=1,...,k\\), is \\(O(nk^ 5)\\); (2) using O(n(log n)\\({}^ 8(\\log \\log n)^ 4)\\) storage it is possible to solve the above half space range search problem in \\(O(k+\\log n)\\) time, where k is the number of points to be reported.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1077166$7506456C-9646-4FF3-9429-C9CFAAC7515D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077166$674FE563-E27F-4C15-8CA6-207F595755D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa4669cf5eaa224b5d3554d9705827ca09f43afb","datavalue":{"value":"52A37","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077166$99542BC8-D266-4C7D-B269-10FAC961F443","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077166$774EA675-9E28-4577-B924-AE9E4397BDDE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a7af6fda7d8fec40c9367d48cb11297c782ec734","datavalue":{"value":"3956453","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077166$0FE00944-09A2-4056-BD13-3DAEA0F033B6","rank":"normal"}],"P16":[{"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":"Q1077166$671506FD-D4BF-44E3-BA3A-E30ECF23C845","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"09a0d0c7c3a8cc7117eaef5e49aac31cce266126","datavalue":{"value":{"entity-type":"item","numeric-id":414867,"id":"Q414867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077166$FA8FB51C-270B-4F10-BC8C-E5D56ED87D70","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":"Q1077166$00B48D2B-DC5B-4A2F-8ADC-696B758AEF1A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9151d6d4e2ff521df32794dada1fcf7423a6bb2","datavalue":{"value":{"entity-type":"item","numeric-id":1253102,"id":"Q1253102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077166$313F74AF-32EA-4235-AF4F-04A18FFCC102","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc1665a29c49afb002e052e9afa5a108aae8ee59","datavalue":{"value":{"entity-type":"item","numeric-id":3727397,"id":"Q3727397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077166$66691492-18A5-4291-A5EF-EE7963192E3A","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":"Q1077166$27E33FFA-B9E0-4F15-BCF6-E83ED451E9A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0bb2a78ba34e8728e91d77da2bf6df4e36bb56c","datavalue":{"value":{"entity-type":"item","numeric-id":3740283,"id":"Q3740283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077166$253888D5-A885-43D8-AF2A-523429899FE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66099c2b34cf2843435b2108529552b54a75963c","datavalue":{"value":{"entity-type":"item","numeric-id":5672661,"id":"Q5672661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077166$182BD3DE-0E18-419F-8799-7B81055F72D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86bd27ab57f23d3defbb32a5ccb58822295dd2e8","datavalue":{"value":{"entity-type":"item","numeric-id":3953183,"id":"Q3953183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077166$1FEF2238-038E-48E2-A078-BCA83AF73356","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":"Q1077166$5C43E1AA-EB90-4BEA-A4DF-DC91395B7CFF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"da9c44e73cf72a89d8cc0380872ad842d3847c8c","datavalue":{"value":"W1996570135","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077166$D9A06A36-A0EF-4881-AB12-51F9E60392DB","rank":"normal"}],"P1643":[{"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":"f144ea14363bcf12b1ae9843a656395e97836ad8","datavalue":{"value":{"amount":"+0.8309608101844788","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":"Q1077166$25A289F8-21ED-4465-8732-90F271751649","rank":"normal"},{"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":"bb703660a9b65ce788c5fe84e2873d6e6587ca15","datavalue":{"value":{"amount":"+0.8254790902137756","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":"Q1077166$71194009-AA17-4A78-8093-8C96C70F436A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d19d1e64fde974c03a20e93c128aa6676ec84450","datavalue":{"value":{"entity-type":"item","numeric-id":4525264,"id":"Q4525264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03286982de9e1b95b0b3261a26e1ee49f5f86a85","datavalue":{"value":{"amount":"+0.8252913951873779","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":"Q1077166$6C403149-24C7-4EA4-8666-2FA9FCCAD5F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e7947784b58dd0387f2e8b8fe2383c2bc057e92","datavalue":{"value":{"entity-type":"item","numeric-id":1329188,"id":"Q1329188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5609c4c920faae292e9f84f9cf7535f1eb0ef1d","datavalue":{"value":{"amount":"+0.8200854063034058","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":"Q1077166$B24FD4EE-1DE2-437D-BD60-5FCC4D578AB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc0352ccb12ffd376a97efe70a68e8326d8da9eb","datavalue":{"value":{"entity-type":"item","numeric-id":5946377,"id":"Q5946377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55f764ee6bfda05b225df8e4fc0275d57be43eef","datavalue":{"value":{"amount":"+0.8139645457267761","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":"Q1077166$32731BA8-10AC-4758-8ECE-143584902418","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1077166","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1077166"}}}}}