{"entities":{"Q1098306":{"pageid":1109058,"ns":120,"title":"Item:Q1098306","lastrevid":66126150,"modified":"2026-04-12T07:43:30Z","type":"item","id":"Q1098306","labels":{"en":{"language":"en","value":"Zooming by repeated range detection"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4037232"}},"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":"Q1098306$AE8EFB1A-696B-441A-8686-6ADA5B46CEB5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9699117bdbbe9bf92a81ce54ae1d6f65604ba145","datavalue":{"value":{"text":"Zooming by repeated range detection","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1098306$04D3CAC0-E7A3-4BED-8861-609D1A036590","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d2bab2b1fb9afb6c8fd10d0b6717cb006f08ddc5","datavalue":{"value":"0636.68079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098306$0FED5C01-E281-465F-BAFE-5494EBABF031","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6e66c630608db4c8883086b40c65b0423f7a3f14","datavalue":{"value":"10.1016/0020-0190(87)90120-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098306$E5D2C2F1-C453-4EBD-B148-E5BCC911F5B0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3f813421ca1324eea7267dc8879260a77170dbb2","datavalue":{"value":{"entity-type":"item","numeric-id":419362,"id":"Q419362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098306$24F2C974-1734-40D6-BB6C-719B16C96C0E","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":"Q1098306$C9C0C38D-98C3-4060-BC61-F1F4DC89DF53","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":"Q1098306$9C1A201F-442B-49E4-A646-891D0C32A680","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":"Q1098306$BD277AFC-CF7F-4468-B721-AE4528A9699F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0820d9af07176cc3fe767d8906d9cc4fcf4020b4","datavalue":{"value":"https://dspace.library.uu.nl/handle/1874/18634","type":"string"},"datatype":"url"},"type":"statement","id":"Q1098306$9B087E70-E0C1-4345-818F-597024BD6587","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"164f4981429d7374252f43b7b491b3d22b0cc131","datavalue":{"value":"In a number of recent papers, techniques from computational geometry (the field of algorithm design that deals with objects in multi-dimensional space) have been applied to some problems in the area of computer graphics. In this way, efficient solutions were obtained for the windowing problem that asks for those line segments in a planar set that lie in a given window (range) and the moving problem that asks for the first line segment that comes into the window when moving the window in some direction.    In this paper we show that also the zooming problem, which asks for the first line segment that comes into the window when we enlarge it, can be solved efficiently. This is done by repeatedly performing range queries with ranges of varying sizes. The obtained structure is dynamic and yields a query time of \\(O(\\log^ 2 n)\\) and an insertion and deletion time of \\(O(\\log^ 2 n)\\), where n is the number of line segments in the set. The amount of storage required is O(n log n). It is also shown that the technique of repeated range search can be used to solve several other problems efficiently.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098306$6DF6C7C0-FD9F-46A7-B28E-E506038DAF50","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098306$2304C511-0323-4223-9721-1FE8E4769BC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098306$F5CE09DD-FF14-4AC7-900C-C6E5357738E5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"953da8fe330e03c40561723d1a7f30291d1ca1ee","datavalue":{"value":"4037232","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098306$0A6EE147-0AE0-4F6C-AE32-B135FB3323C8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e13226896772781f16a7d6061185ca399b94694e","datavalue":{"value":"range searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098306$A20C794D-C536-4CCE-B2F6-61ABF1E3D4D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d52723300c2e4a19b38372197a0a9e2dd175451","datavalue":{"value":"nearest neighbour searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098306$7DD97233-EE77-441B-A466-D8F0AF0262D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098306$23D84E38-4214-42D7-85DB-A0BBDA3FFCCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"423372722ffce52d92ff0a29cab429fa342d34e2","datavalue":{"value":"computer graphics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098306$FEE65928-2003-4C16-A0A7-F2FA745DC6D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b76fa601f06bb0745a1c99fe7296e00ac05b27f","datavalue":{"value":"windowing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098306$9DF501E6-70AF-4765-ABCF-0F85E195CF61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03643b3cd0ead3fad9c38d16b73cb3581a239813","datavalue":{"value":"line segments","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098306$6D550582-843F-40E7-9C1E-04E355202FBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"856192546dfbe800ef42652d3d43e7d2418fc742","datavalue":{"value":"moving","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098306$25758260-EE2F-4354-89BA-9C074E5FDDAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dd1949c389d63752d37e39c088455a19166352c","datavalue":{"value":"zooming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098306$6320DB05-71D0-41BA-99FD-51CD0EB201FD","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":"Q1098306$EBD9AE2C-E054-4A97-8DD4-AA3D4F295B4F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c9267a7ea72ebe1bb0251babc542b756c1deffc4","datavalue":{"value":"W1996074398","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098306$15EB6D0A-3461-42A1-9C46-5B8DB5CE0F93","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8b0d9b102c54c9266371ad3fbd6cfce4c17b7bd","datavalue":{"value":{"entity-type":"item","numeric-id":3735085,"id":"Q3735085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098306$B04AEE53-31A8-461E-B1D6-B438B8F24625","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":"Q1098306$4F1E8040-B96E-4A80-826F-4DB5BF3EB77C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cd1462286ac5df294dbd58d9be71779e0279c3c","datavalue":{"value":{"entity-type":"item","numeric-id":797269,"id":"Q797269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098306$DA8D4D87-C3E4-4B59-8EB3-CEC4078B91D4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab5618564f35cd8090cc41070b6e62515d883e08","datavalue":{"value":{"entity-type":"item","numeric-id":3687756,"id":"Q3687756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06609192e3c6538e9f8d6586f8ca370f11aca5a0","datavalue":{"value":{"amount":"+0.7711041569709778","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":"Q1098306$E416A37E-3FFE-4134-8799-FE49A38146D4","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":"773b1baa4082051cc3b74fe41fffbf19a376faff","datavalue":{"value":{"amount":"+0.7660846710205078","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":"Q1098306$5EA6D589-0493-4189-A12B-21B49999DBBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5681b5bd757804d9cfc63c7ddb19bfcd1d88b91","datavalue":{"value":{"entity-type":"item","numeric-id":3735085,"id":"Q3735085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47f5b800e4b7a089a68512f2ee69d448a9285c23","datavalue":{"value":{"amount":"+0.7551499605178833","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":"Q1098306$1F9D92B1-341B-42AF-B907-76ED7CD22AF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4eaa94b41871c59ce55c894b7752663d6f1e30cb","datavalue":{"value":{"entity-type":"item","numeric-id":4225298,"id":"Q4225298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c944d3f42a9c08d6342afe0abe7b37a1442287c","datavalue":{"value":{"amount":"+0.7516858577728271","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":"Q1098306$A29A8B08-ED0A-4BE2-B06D-9CBAD2A44885","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bd2b22ffda7dba83e7bb213ef556ac04a9a1719","datavalue":{"value":{"entity-type":"item","numeric-id":4201934,"id":"Q4201934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65b4487eacf5f8a7feafa6e38f922e05bfaf4836","datavalue":{"value":{"amount":"+0.7447366714477539","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":"Q1098306$D7A3B667-8B97-4C8B-B429-91DF7DCA9D35","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Zooming by repeated range detection","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Zooming_by_repeated_range_detection"}}}}}