{"entities":{"Q790614":{"pageid":792462,"ns":120,"title":"Item:Q790614","lastrevid":48687268,"modified":"2026-01-05T15:01:00Z","type":"item","id":"Q790614","labels":{"en":{"language":"en","value":"Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3848610"}},"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":"Q790614$0C039E0E-4BA0-4BE7-B516-872F9045EADD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5cf2c10fd980d5123410968ae68702c19b26420f","datavalue":{"value":{"text":"Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q790614$016D0054-6C1B-4F8E-822C-8BFDD8670536","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9b174d96c18c3ca00fdace04ebe845351413c413","datavalue":{"value":"0534.68031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790614$9F5B068A-9EE6-479D-B7B7-56ED1AB36B0B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"46f70603e015b7011639bbf52795b4247964d34b","datavalue":{"value":"10.1007/BF00264251","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790614$B1FB4BB6-DFDE-4A02-9905-8E95F042F543","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790614$47FA9011-4326-411A-85C7-580F2133E9BF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q790614$4F41FE74-8B60-458D-8BA6-3EA8859F0CB2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"25f5cbf40159fe8a15780880837eae5834212502","datavalue":{"value":"We consider two geometrical problems that have been solved previously by linesweep algorithms: the measure problem and the contour problem. Both problems involve determining some property of the union of a set of rectangles, namely the size and the contour (boundary) of the union. We devise essentially a single time-optimal divide-and-conquer algorithm to solve both problems. This can be seen as a step towards comparing the power of the line-sweep and the divide-and-conquer paradigms. The suprisingly efficient divide-and-conquer algorithm is obtained by using a new technique called ''separational representation'', which extends the applicability of divide-and-conquer to orthogonal planer objects.","type":"string"},"datatype":"string"},"type":"statement","id":"Q790614$0A7B2795-28C3-4B88-BAB4-372EFA2C78F3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790614$D76CD233-C633-4198-BFD8-26D034009065","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"41ddab1d6602ba11b076d30b7ecfa21176a89be6","datavalue":{"value":"3848610","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790614$5DE60266-7FE7-4334-AEF3-E2F45EFDDCEC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q790614$46F0F0BA-F89C-46E0-A75E-9B466A01C141","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b7547c11552896e9115ebd14fef7a7845fae260","datavalue":{"value":"measure problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q790614$4F2614A8-F7A5-42B3-8A30-9B9F665405E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dea091764d0de155a407f712ad269cd8eda38ce3","datavalue":{"value":"contour problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q790614$9B46E159-5BCD-46A4-BDD0-30EA875EB0EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3d96e3d74138447af545d0cb2d3866006bca24c","datavalue":{"value":"rectangles","type":"string"},"datatype":"string"},"type":"statement","id":"Q790614$B6F989B4-4DF7-4F00-86E1-F903B0AF8638","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ceec4f6ab6dde56c582e3d6cb2cd2bd1ccaae93","datavalue":{"value":"divide-and-conquer algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q790614$007188FB-F746-4CBE-BC17-F412DFD67722","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35717b3987003562580d0e02156748f819427d46","datavalue":{"value":"separational representation","type":"string"},"datatype":"string"},"type":"statement","id":"Q790614$E98311DF-724C-4570-BD52-B69A8A56250B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f512411db4da82caa205f65c84c26b9a11e92117","datavalue":{"value":"orthogonal planer objects","type":"string"},"datatype":"string"},"type":"statement","id":"Q790614$2D8B18C5-AF12-4DE6-8E75-068E0BEC8DDD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8f8f9ae2c8e7688fb664db2e624732ddf1a8713c","datavalue":{"value":{"entity-type":"item","numeric-id":1171388,"id":"Q1171388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790614$28AC1BC7-A09F-4DDB-B976-A9016E8E5C08","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":"Q790614$FEB04B1F-B95B-4DE1-929C-D42EFA5153C7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790614$A3828941-5881-481A-AB44-B7F93A963A34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90c10f3313dde19a9252305df9d45bc029891d9e","datavalue":{"value":{"entity-type":"item","numeric-id":3049855,"id":"Q3049855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790614$C2CAB53A-7417-4959-BEC6-06743441B8BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e15dd9946405b881f07537d812794e207c18c348","datavalue":{"value":{"entity-type":"item","numeric-id":3339305,"id":"Q3339305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790614$D50F1863-FDE9-4490-91AA-4D6A6AADA3AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"802c9c8693bad2c21286f8d3eae6b5e1f4e7123f","datavalue":{"value":{"entity-type":"item","numeric-id":3323293,"id":"Q3323293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790614$94E940F0-4B34-4855-808A-2BF93D7F2E91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26248a4d0d5f12c17071bbb72b87f0b72d350b60","datavalue":{"value":{"entity-type":"item","numeric-id":5904922,"id":"Q5904922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790614$8FE580AF-B0C4-4758-892A-6FBDF0575E15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51198c5ee71c97a3ec1fffeadf84de9587c8db3b","datavalue":{"value":{"entity-type":"item","numeric-id":3336711,"id":"Q3336711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790614$3D97C9FC-F346-4CAF-8460-1EBF41E94E48","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0f4d38c81a169c759cc3ce01759048b875db764d","datavalue":{"value":"https://doi.org/10.1007/bf00264251","type":"string"},"datatype":"url"},"type":"statement","id":"Q790614$BF2EBF11-9B2A-4086-BED5-1052F49737AD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"11cd60fb8051ef7c880c7fc7e9ba7c246d2f9ab9","datavalue":{"value":"W2294023352","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790614$889DFB6F-27DD-400A-A5AA-98A8FD000814","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b10f851821e7177122edeebc7493734d13ed92c5","datavalue":{"value":{"entity-type":"item","numeric-id":3316614,"id":"Q3316614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d73637c5622e29f8ee35f08a7f0401f3748d4d21","datavalue":{"value":{"amount":"+0.9950734972953796","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":"Q790614$7BE9AA11-04F2-4D2C-A6FC-E9D82B003DC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9540ab3425c9412dd70828a08feae788dd949ad","datavalue":{"value":{"entity-type":"item","numeric-id":3802611,"id":"Q3802611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c2f6058ca0c4e99fcf02f4f8bc428b80811ca34","datavalue":{"value":{"amount":"+0.8725326061248779","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":"Q790614$868B1AA1-DB5D-40EB-85FA-A07D97BDFF32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"833a6496a9ec23dfad3ec7b48150089cd9be7b18","datavalue":{"value":{"entity-type":"item","numeric-id":3339305,"id":"Q3339305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49029cbb75b973c4c3bd7acd6e5d99763e768470","datavalue":{"value":{"amount":"+0.8266712427139282","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":"Q790614$FF60851B-BBA5-46A8-A0A3-61799D95D34F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0712b9ba18e4be5c084def869e696bbeef0a2988","datavalue":{"value":{"entity-type":"item","numeric-id":802313,"id":"Q802313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7e621583c542a82f0e491c986b356c01a5f374d","datavalue":{"value":{"amount":"+0.8085922598838806","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":"Q790614$8188F91C-83E3-4D67-BC65-4F1DB0AB24F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efb2c5bed86c071fb8f5e2174d347973a0c0a619","datavalue":{"value":{"entity-type":"item","numeric-id":1108000,"id":"Q1108000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"520cf68ec3600bd712f5219afbb5872062a70226","datavalue":{"value":{"amount":"+0.8078414797782898","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":"Q790614$9D765C7E-CD86-4D7F-BCC5-A695F3241A8A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:790614","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:790614"}}}}}