{"entities":{"Q578916":{"pageid":580683,"ns":120,"title":"Item:Q578916","lastrevid":62914908,"modified":"2026-04-11T08:58:24Z","type":"item","id":"Q578916","labels":{"en":{"language":"en","value":"Linear space data structures for two types of range search"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4014041"}},"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":"Q578916$9BCEDB1C-B1C2-45CF-B81B-ED03F2FAF3A8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8cea48cae9081835622529329b1fd5cb7b6eb6ba","datavalue":{"value":{"text":"Linear space data structures for two types of range search","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q578916$336DF413-5080-4FAD-96EA-148C0CD0F84E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ab51baac407edcc0c2758e5f2c58fc4fe9b2c826","datavalue":{"value":"0624.68054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578916$2F19DD12-9809-4B6B-ADEF-014A39880333","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1e192abf583776cd6fc1d7cf3cb215f6af28f344","datavalue":{"value":"10.1007/BF02187875","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578916$0A637436-C4AE-4FC2-88F2-37F60EAC64A9","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":"Q578916$AB3F3140-D52B-4C18-A43F-65BF2E591A3F","rank":"normal"},{"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":"Q578916$8A8F17CE-DB5F-4875-96D4-C54A510E6208","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":"Q578916$385F93C3-4FEA-4786-8715-B156DB219569","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q578916$30840280-2AED-43AE-A405-3E3057480FB0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d92453be5cd7ab60f7d416719260ba18b34d1543","datavalue":{"value":"https://eudml.org/doc/131014","type":"string"},"datatype":"url"},"type":"statement","id":"Q578916$A4470633-6A34-4989-9E4A-82C846CB4B3B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1e89f9bd3a157e8dafeeabf7ecfe54aa7c102108","datavalue":{"value":"F\u00fcr den zwei- und den dreidimensionalen euklidischen Raum werden Aufgaben der ``Bereichssuche'' betrachtet: Seien eine Menge von n Punkten im Raum und eine Menge von Teilbereichen des Raumes gegeben (im \\(E^ 2\\) sind dies in dieser Arbeit alle Dreiecke, deren Seiten parallel zu drei gegebenen Richtungen sind - im \\(E^ 3\\) sind es die unendlich gro\u00dfen Oktanten, die sich von einem beliebigen Punkt aus parallel zu den Achsen jeweils ins negativ Unendliche erstrecken). Gefragt wird nach der Komplexit\u00e4t der Algorithmen, welche alle Punkte der gegebenen Mengen ermitteln, die in einem der Teilbereiche liegen. Als neues Resultat k\u00f6nnen die Autoren angeben: Der ben\u00f6tigte Speicherplatz hat lineare Komplexit\u00e4t O(n) und die Bearbeitungszeit f\u00fcr eine Anfrage im \\(E^ 2\\) bzw. im \\(E^ 3\\) verh\u00e4lt sich wie \\(O(k+\\log n)\\) resp. \\(O(k+\\log^ 2n)\\), wobei k die Anzahl der gefundenen Punkte ist. Erreichbar wurde dies durch einen aufwendigeren Vorproze\u00df, welcher die gegebenen n Punkte in einer baumartigen Datenstruktur ``vorsortiert'' und der sich bei vielen Anfragen gewisserma\u00dfen amortisiert.","type":"string"},"datatype":"string"},"type":"statement","id":"Q578916$20384C31-C753-4D5C-B8D2-5B3BF667FD83","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578916$901E62C8-47FE-4531-B57F-129C150137A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578916$792636D5-DF0A-493F-9F36-EC091D7071A4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"58636e006bd9cec65ca0a40f09e853e9603164f6","datavalue":{"value":"4014041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578916$7F51FFB4-2A4F-4E74-8498-72FA8781011A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d6c2cc6f07064ec8ae1740d4bb24f6665008113","datavalue":{"value":"linear space data structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q578916$6DA763C3-A508-491F-8B41-8EC22DBA8B7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e13226896772781f16a7d6061185ca399b94694e","datavalue":{"value":"range searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q578916$9D9ACB44-888C-40DC-A077-785C82086AE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"530eb769604af13ed7b7eab30bbbd87f7e15a255","datavalue":{"value":"homothetic range search problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q578916$60DDAECF-CFAF-4EDF-A61E-AAB4E8622836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1315f15f86731ec78d26e13a5c5958e60ef485c9","datavalue":{"value":"domination searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q578916$BC1108C0-113A-41A5-8991-56F5D2CEEACE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q578916$A2DA1A67-4D87-457A-AD58-73862033929B","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":"Q578916$009D4DFC-921F-4123-A1EC-02A5E4DF9E9D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3dc7eb8caf969204b8972e6206e244f9c8f10485","datavalue":{"value":{"entity-type":"item","numeric-id":148390,"id":"Q148390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578916$B8F8F5A1-D32D-493F-9902-BCB0B85D5206","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd2eefc175d55ef5b4fe824717af8023e20e88fa","datavalue":{"value":{"entity-type":"item","numeric-id":3753527,"id":"Q3753527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578916$42EE7F47-5073-499D-84EE-737E15238DBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be1854206526a8f5ce07f2af8ef7885505eb7dfb","datavalue":{"value":{"entity-type":"item","numeric-id":1062772,"id":"Q1062772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578916$487DC6F0-D324-42F7-89FA-71296CB030F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76ce173cdd6420ed78061b92000307f2e179c306","datavalue":{"value":{"entity-type":"item","numeric-id":1099957,"id":"Q1099957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578916$B6AA7991-AB6A-42A4-9850-D14FE8A8EF2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb71e38ab0216024ec0690b1685e409899a3aead","datavalue":{"value":{"entity-type":"item","numeric-id":1082821,"id":"Q1082821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578916$B13DDDC2-3C93-4761-BFFE-12F250871B66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcd35a1fd3af99492727136bdc8d532d451ebf6d","datavalue":{"value":{"entity-type":"item","numeric-id":1097038,"id":"Q1097038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578916$B868EFF4-06F5-4FD0-9EB2-F14622AFCCCA","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":"Q578916$31DEAE02-F980-4A8B-8E9B-4FB722DC28BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ff4e812fbcc008a1d5259e712cd9203d973f596","datavalue":{"value":{"entity-type":"item","numeric-id":3711764,"id":"Q3711764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578916$C26FC728-D8FB-48BA-A789-9742F6778AB7","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":"Q578916$2F55A1BF-D8B6-4CAB-93CB-C33C827D4E85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4cf1cbc903427b9dfc0dbb5cfe0f58382818bfac","datavalue":{"value":{"entity-type":"item","numeric-id":4077449,"id":"Q4077449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578916$4E5E19BB-B709-431B-BA57-4BE6002A2908","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a2a57b475ae76d5a53ffe9b99df300f7fdeea33","datavalue":{"value":{"entity-type":"item","numeric-id":3906439,"id":"Q3906439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578916$CD2A6321-7559-4D47-BBD8-ABE03694141A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cdc80085f51274788196b5be4e7f9615585e8b2f","datavalue":{"value":{"entity-type":"item","numeric-id":3678686,"id":"Q3678686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578916$7F577A38-DBB4-4F1E-B247-A95F69804E2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53270a197dc74dec5db368885ae5da2d9b50fbb5","datavalue":{"value":{"entity-type":"item","numeric-id":1253450,"id":"Q1253450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578916$4310738A-E8AE-40F4-B83C-28803368DFDD","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":"Q578916$0C8FC765-EE06-49B2-8866-3BDF2044E8A1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a829ed48f3d746e2f8766ad930b7c3f58ff883e7","datavalue":{"value":{"entity-type":"item","numeric-id":1005331,"id":"Q1005331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14abdefbac00a1ad857e355cc1665499bd8d8003","datavalue":{"value":{"amount":"+0.8133506774902344","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":"Q578916$76FFA2E6-0192-4163-A1A9-9778ECC62037","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48342537a955ab5d15038ce9aafd07d79151d553","datavalue":{"value":{"entity-type":"item","numeric-id":1107313,"id":"Q1107313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da21b10c4e59c8334a08e6a1989480e3980a7f2d","datavalue":{"value":{"amount":"+0.8100000619888306","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":"Q578916$A0825220-DB1A-48F0-9DEE-5E7E723DC0D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccd9a5e80c271249abd199fb0a6958008f7ffe63","datavalue":{"value":{"entity-type":"item","numeric-id":2583568,"id":"Q2583568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6d8f29aa0e832bffa250fe7ccc959618d67244e","datavalue":{"value":{"amount":"+0.809018611907959","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":"Q578916$908D806E-BA03-46D5-8B2A-7A9DBB0CD9B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e617c149a88aab67f4f95b13018391e85f17a5b5","datavalue":{"value":{"entity-type":"item","numeric-id":3603510,"id":"Q3603510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4f7c85e7dd7759dfc9559dba4c51c9c2ee34df7","datavalue":{"value":{"amount":"+0.8054798245429993","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":"Q578916$4FF25E17-1ADF-4E5E-AF06-1CD6B1673825","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4efa68780616eee8f67b10fb3a13bab1d059e5ae","datavalue":{"value":{"entity-type":"item","numeric-id":3777465,"id":"Q3777465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b9db79117bbbedf3762ca27038a23c3d43626a3","datavalue":{"value":{"amount":"+0.7929601073265076","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":"Q578916$6728D17C-1C64-475C-919F-A0AE1079C4FF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Linear space data structures for two types of range search","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Linear_space_data_structures_for_two_types_of_range_search"}}}}}