{"entities":{"Q1421031":{"pageid":1431771,"ns":120,"title":"Item:Q1421031","lastrevid":67405446,"modified":"2026-04-12T17:24:42Z","type":"item","id":"Q1421031","labels":{"en":{"language":"en","value":"Speeding up the incremental construction of the union of geometric objects in practice."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2031378"}},"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":"Q1421031$6E2F97FC-91EE-44AE-97E8-6027AAC8F52D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"68916aa72fd0f087f1c474bb9b92f5e9f4a1e1e2","datavalue":{"value":{"text":"Speeding up the incremental construction of the union of geometric objects in practice.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1421031$4FF2D1EC-1DBA-430D-A27D-2F1D53618065","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5385ba470f45834289e516b6a1a1fdf0d777ed59","datavalue":{"value":"1039.65019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1421031$9F566EEB-B0A1-4D6A-A39E-2F7FD1427841","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"94ada511e407e5c76148a61d88f66447b93c7003","datavalue":{"value":{"entity-type":"item","numeric-id":1421030,"id":"Q1421030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421031$C5419796-B9E8-405E-A366-F3C7E3095CD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"23a41a6deabd7061042ee0e831f408aaabaf33af","datavalue":{"value":{"entity-type":"item","numeric-id":238435,"id":"Q238435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421031$54E5B774-A638-43BF-995F-363F82F01BCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"05973d4747711a904c4eb354f325fda834906623","datavalue":{"value":{"entity-type":"item","numeric-id":396765,"id":"Q396765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421031$33FA0BA1-4C42-4020-9589-25239E6D6ACF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421031$D8BCF5DA-114B-425E-ABD7-F21C56F5141D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8e953e40a98762a68bef74ffc60d05e25f086206","datavalue":{"value":{"time":"+2004-01-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1421031$D6525AB2-29AD-4BEC-9686-8EC05CCA0861","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c6b712979770fd3e5b37151a76b68b25010041a9","datavalue":{"value":"A new incremental algorithm called disjoint-cover (DC) algorithm for constructing the union of \\(n\\) triangles in the plane is given. Experimental results are presented to show that DC algorithm performs better and significantly better in some cases than the randomized incremental construction (RIC) of the union. It is also observed that the DC algorithm can be generalized for other geometric objects in the plane, and also can be extended to higher dimensions.  Very recently the authors have also applied the DC algorithm to the problem of constructing efficiently (in subquadratic time) the union of \\(n\\) triangles when the union is determined by only a small (unknown) subset of the input triangles. This has been reported in a work by \\textit{E. Ezra} and \\textit{M. Sharir} [Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Alogrithms (SODA, 04), SIAM (2004)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1421031$B27C063A-81A2-43A5-AC3D-DC5C84C4EA62","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"956419f6fd71b8dac027f33d0ad5be15c64817eb","datavalue":{"value":{"entity-type":"item","numeric-id":182524,"id":"Q182524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421031$3623C832-663C-4D3C-8855-A1EDD920A255","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1421031$10336C3B-84D1-4D87-B293-B6FD44D37EC5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6716dcce294cbdd5e58a70f9ed6024e605b40b08","datavalue":{"value":"2031378","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1421031$8DA6B936-4E7F-4CBB-A644-34ABF7A09D17","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5a75e5d12525f6497c5f027b1ec7e5358653584","datavalue":{"value":"Union of geometric objects","type":"string"},"datatype":"string"},"type":"statement","id":"Q1421031$8BEDD4B9-59E1-4D6E-A9AC-E10A2809D1B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d4d4d9863fad73d4c5b18d81af8cd0585cb60dc4","datavalue":{"value":"arrangements","type":"string"},"datatype":"string"},"type":"statement","id":"Q1421031$BE74F0F5-0314-4A2A-9974-BAD5ED991022","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"679372600590a03c48d4032113dc215d14bd33c6","datavalue":{"value":"randomization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1421031$5125983D-FDC8-4DC0-B747-78BF488A1630","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c0894c225a8410d87eabba71ed99d69e4091950e","datavalue":{"value":"exact computing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1421031$B7A1AAA8-BF37-4A46-A0D2-7F10E5958C38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36136d5be61d5441cd46b645b75e781082fe9956","datavalue":{"value":"algorithmic engineering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1421031$BD6DA606-EE2D-4EAE-AD4F-EE7498FFD5E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d74cb5419439f42eb1ba8891c8722bd3702922d","datavalue":{"value":"numerical examples","type":"string"},"datatype":"string"},"type":"statement","id":"Q1421031$A8E51FA1-5B71-4FC2-B2AC-1D11DBA4E80A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9e959bbcb6247aa3d32e507d6ce5a7943a24cbbb","datavalue":{"value":"disjoint-cover algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1421031$CEDB0742-C932-44D5-B434-45F97FBCE372","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e9e35d6c3318040b64771639cb9cc8dafefc1ca1","datavalue":{"value":"randomized incremental construction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1421031$9B30ED1B-21F8-48FF-B3D7-BD84E498CC93","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"8970d53f5fc5de8a7599b5d4b50f76cbd183814b","datavalue":{"value":{"entity-type":"item","numeric-id":13265,"id":"Q13265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421031$EEDDF7EA-88F0-4E0D-890A-FAD0D8A4D768","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":"Q1421031$70E30E45-BBE2-4249-A17B-B08F5841E1EF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cadb4ed6eecdc5d84940f97cfc33fafe213d7e17","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2003.07.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q1421031$28C19AB3-5ABD-4B0A-B205-C54E491678A8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d6e75e3f79f433b7e349525bce533fa31380a2e6","datavalue":{"value":"W2002581612","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1421031$D21A3682-B218-45B9-A7DD-43D3FF749576","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0d029af071a8946ee1662887e0e0b0ab0a7ae3b","datavalue":{"value":{"entity-type":"item","numeric-id":4344150,"id":"Q4344150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421031$B243A6BC-F8C9-4D28-A766-C858A6519C66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cf652e387889ff8257b822083279dfef17e7ff7","datavalue":{"value":{"entity-type":"item","numeric-id":5501288,"id":"Q5501288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421031$06169AF6-CC76-4AA6-BA8F-3A1760793E49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f4ba771dac290a164052bbd8205a42e589a3f10","datavalue":{"value":{"entity-type":"item","numeric-id":1903639,"id":"Q1903639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421031$B6EBA4A2-10B0-4A9C-813A-CF3D6CF7A30D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae29f327c59780dea378339b809ffb2bf6e4bd12","datavalue":{"value":{"entity-type":"item","numeric-id":1076976,"id":"Q1076976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421031$DCB3BC8D-EA73-4D19-8566-B48ACDF96D3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0b2d77efe01890b2cef4fd0c4157d026bd2bd17","datavalue":{"value":{"entity-type":"item","numeric-id":4286234,"id":"Q4286234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421031$AFD59EB2-5005-4CB6-9FB1-6F1DE66D49D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f008ff6ef8ff17ba2dc931dfc3da0de1a1cc1976","datavalue":{"value":{"entity-type":"item","numeric-id":4339095,"id":"Q4339095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421031$32F5EAF0-8A76-424A-B1C4-CD64AC5B29D9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"52700f354b001637439582082af29a9bd168ff10","datavalue":{"value":"10.1016/J.COMGEO.2003.07.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1421031$3073E251-4492-464C-83C5-F575B8F8EB71","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c93caa0b2a1bff57b8db11c6259f99402577a6f","datavalue":{"value":{"entity-type":"item","numeric-id":4411384,"id":"Q4411384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b948782ad59f9fc90b58c6350a796d686cec879","datavalue":{"value":{"amount":"+0.9910414","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1421031$F0A649D5-8956-467E-9F97-C3E5F9C22469","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8dc91f354c9851ea5d15650a91f13d71d9d18ce3","datavalue":{"value":{"entity-type":"item","numeric-id":4547818,"id":"Q4547818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e06a833b03c2a485339b225ed27c4cf38097c27","datavalue":{"value":{"amount":"+0.8697067","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1421031$81EFA1CD-573F-4103-8BA6-740FEC5664DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82375475a5ed136571fb76476f1fff969481e4bf","datavalue":{"value":{"entity-type":"item","numeric-id":1894301,"id":"Q1894301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abbac14fccd1b1043d077a8d5a4d938896031c17","datavalue":{"value":{"amount":"+0.84840655","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1421031$B772B802-8524-47EE-BDA1-EE59C319B133","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9c715d10aa92255fd43db421f8d330fcdb477e6","datavalue":{"value":{"entity-type":"item","numeric-id":5361676,"id":"Q5361676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ddc8c768df4234160ccc859d619724a136a2e43f","datavalue":{"value":{"amount":"+0.84536976","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1421031$1E7D0B21-E690-4DC5-8E20-4BB7A1B3598E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"888f0faa0ff0447f4c54193c537d38f8f4e8aaf7","datavalue":{"value":{"entity-type":"item","numeric-id":2354921,"id":"Q2354921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5881cc9fcfc0cc392fa79ff74af592100ece4bc3","datavalue":{"value":{"amount":"+0.8430977","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1421031$F5E0687E-FA06-44EA-A104-071454102920","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cda1a9ff828cb7f32dc63a890f5a29fc5b30e87f","datavalue":{"value":{"entity-type":"item","numeric-id":5174490,"id":"Q5174490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5881cc9fcfc0cc392fa79ff74af592100ece4bc3","datavalue":{"value":{"amount":"+0.8430977","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1421031$5C5C148A-B1B5-4BCE-8386-043C631EC928","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab742292586a9b902959c7b73dbb23d265651f80","datavalue":{"value":{"entity-type":"item","numeric-id":2848977,"id":"Q2848977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb83bba2dae66a4009aee52d922cb6c891482b70","datavalue":{"value":{"amount":"+0.83480155","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1421031$24051A3B-E731-4105-8300-1E766AF76019","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b594ff46795bc7b8bce0c9b885a28965d54d937","datavalue":{"value":{"entity-type":"item","numeric-id":1860195,"id":"Q1860195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d59e89487a59585a984a26d686438aaa4f3407dc","datavalue":{"value":{"amount":"+0.8279199","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1421031$8F4BF487-22D4-42A3-8EB1-002E36C878CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59e23ce7cd0880b8c1c94756a94440c9b74c3de9","datavalue":{"value":{"entity-type":"item","numeric-id":2486080,"id":"Q2486080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d70d190ffaa573f7a3781a5959b5711d62f262c","datavalue":{"value":{"amount":"+0.8251404","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1421031$0DF4CC45-B877-44BB-B75A-4C7D0F536EA6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Speeding up the incremental construction of the union of geometric objects in practice.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Speeding_up_the_incremental_construction_of_the_union_of_geometric_objects_in_practice."}}}}}