{"entities":{"Q802313":{"pageid":804161,"ns":120,"title":"Item:Q802313","lastrevid":64486584,"modified":"2026-04-11T20:11:57Z","type":"item","id":"Q802313","labels":{"en":{"language":"en","value":"The contour problem for rectilinear polygons"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3890751"}},"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":"Q802313$1CCA6700-567C-4841-8BD3-446DFD9707F0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4b112a628dc782665613d64eba70d5d3032fb19d","datavalue":{"value":{"text":"The contour problem for rectilinear polygons","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q802313$0E2BA2E8-B5A9-498E-9FA6-D80D6FBE54EF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d227d30919a027cf3fe23e17cfbfee902cd811d3","datavalue":{"value":"0558.68059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802313$68AC66CF-65C2-46EE-967C-AC6E2DD4137C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"43c448ebd89194b1d55b21ed80f62dd69cdff082","datavalue":{"value":"10.1016/0020-0190(84)90058-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802313$4ED7B546-C1AF-479A-8F0C-A63CFFD4A0F6","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":"Q802313$52585B6D-D91C-4BFE-A9E2-EC4D8F95B3AC","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":"Q802313$BA5B3E7F-9A71-4D79-84AB-8EF73AFE0AFA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e21f84cbc34b1f89629331b4e4696d9f430d4d59","datavalue":{"value":"This paper presents yet another algorithm to solve the contour problem for the union of a set of rectangles or orthogonal polygons. The algorithm is both time- and space-optimal, requiring O(n log n\\(+e)\\) time and O(n) space, if the input has a total of n vertices and the output has a total of e vertices. The only other algorithm with this performance is the one due to G\u00fcting. However his algorithm relies on a complex data structure while the algorithm given here uses a simple variation on the segment tree. Indeed when the input consists solely of rectangles the solution is almost as simple as the original and non-optimal Lipski and Preparata algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q802313$6C050893-37A1-48AD-A52E-F8C0A033CD19","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"25fe30a6fe5285f54b3a7ea7d7e97ac0b640e4f9","datavalue":{"value":"68R99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802313$8840325D-D69C-44FB-8A97-D85C55BD73D8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8ef239b8801657d1f6cc08bd853f62a7af3e8ef3","datavalue":{"value":"3890751","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802313$CA45ADAD-43CC-4E71-8A67-FB9965B159AA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc00012563a75ed0c7975e9c32d5f2d16f0982e3","datavalue":{"value":"optimal algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q802313$35B36707-35A8-468B-8BA8-B226EAF1DB2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e98673752e6e86aadffb6110effc84731ac7ac43","datavalue":{"value":"sweep plane","type":"string"},"datatype":"string"},"type":"statement","id":"Q802313$F8B23EC5-8575-4EA5-92C5-467FD71E137F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"83432aed270c0795b0ee1e33eb92bceb340a1a23","datavalue":{"value":"scan line","type":"string"},"datatype":"string"},"type":"statement","id":"Q802313$B0AA92C0-C78C-4787-9D44-31EFEFE250C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"43f1319cf5cc2bf8b1b07d9b280fc1eb5120b6eb","datavalue":{"value":"disjoint-set union","type":"string"},"datatype":"string"},"type":"statement","id":"Q802313$AC786D37-3BAB-4FD2-9CAE-C6EB4DAA0A59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dea091764d0de155a407f712ad269cd8eda38ce3","datavalue":{"value":"contour problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q802313$D61B60FF-FD9B-4662-8F9D-39515FC61ADE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3d96e3d74138447af545d0cb2d3866006bca24c","datavalue":{"value":"rectangles","type":"string"},"datatype":"string"},"type":"statement","id":"Q802313$141CF72B-63CB-4532-84DA-FF3521E12C9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b7b1140a6f42be4b53b8db8ad2ef22f71b47ed8f","datavalue":{"value":"orthogonal polygons","type":"string"},"datatype":"string"},"type":"statement","id":"Q802313$92E7D9FB-9BF3-4A36-BB3B-EB7B48DBDE44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"82441fab5332f16d6ea3b7936b9ed81a306faa84","datavalue":{"value":"segment tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q802313$5CA0639E-BE0D-4021-9CD3-55BE4AA9892C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5a0713dc23156af5d53825dba8b7cf59c3d6e007","datavalue":{"value":{"entity-type":"item","numeric-id":596098,"id":"Q596098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802313$DA6EAFBF-4117-47EC-97F0-58AF8FA016B8","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":"Q802313$95ABD9FE-BC47-4D1C-B01E-7DB88D4851AD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7927b02982dfcbf8e405d468b1101c71b3bdf085","datavalue":{"value":"https://doi.org/10.1016/0020-0190(84)90058-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q802313$C82BC640-8FCF-4406-86CA-56EB6F0F8A54","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b3b80bcacab936c9cf3a57763a2c8522547e083b","datavalue":{"value":"W2005465277","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802313$990F96FE-8E4E-4E85-BCEB-362223CD1300","rank":"normal"}],"P223":[{"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":"Q802313$E7483E55-2097-4B14-9559-3E6E2DE3D09B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11bf99ff7f96911f7a918510092e288781260305","datavalue":{"value":{"entity-type":"item","numeric-id":790614,"id":"Q790614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802313$26B9BDAB-536B-4FC3-A09E-B233D9AD1AFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3899872019c7930c7d863fe2d77e379b34b2be41","datavalue":{"value":{"entity-type":"item","numeric-id":5904701,"id":"Q5904701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802313$39E2F98D-609E-4EAF-A3AE-94EB7373A146","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1432afdb19466581eb592d975972f20a900482ea","datavalue":{"value":{"entity-type":"item","numeric-id":1056548,"id":"Q1056548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802313$2386A709-7E34-424D-8A74-1801D080B765","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c21d3f4480d9b77cb8b6fc1ee154576ecd13816","datavalue":{"value":{"entity-type":"item","numeric-id":3959475,"id":"Q3959475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802313$64619974-43C5-4896-A6D4-520C9567F483","rank":"normal"}],"P1643":[{"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":"1fc0e810e28c2942dfaf0a2f8298de5829a95686","datavalue":{"value":{"amount":"+0.9116966724395752","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":"Q802313$1C2FDA8C-C3BF-442F-A09D-26211F7A2DC0","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":"bb0bc54e0c35e37fd331ccc24cb53e33934eaacf","datavalue":{"value":{"amount":"+0.9096201062202454","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":"Q802313$8CB14352-5C42-471F-8F9F-7D3206D859DA","rank":"normal"},{"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":"3e41eba0dfb3e9a2602e3e034464760c37f2e8d4","datavalue":{"value":{"amount":"+0.8265891671180725","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":"Q802313$740CA167-200A-425B-A80A-60A36B87B490","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ce875f48c529f15efcb54d8809345fd2ed99fd9","datavalue":{"value":{"entity-type":"item","numeric-id":3779343,"id":"Q3779343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbd8ad6009ddb8e673b000e07fa30f8bb6385fa6","datavalue":{"value":{"amount":"+0.8222838044166565","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":"Q802313$56A34AAC-0EE4-4E8B-8D8F-027A8BD6FDFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"419087fa89443f673da618222bcdbd774844377c","datavalue":{"value":{"entity-type":"item","numeric-id":790614,"id":"Q790614"},"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":"Q802313$524E0EDE-1E6E-4214-8F3E-5D2236FA6CF8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The contour problem for rectilinear polygons","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_contour_problem_for_rectilinear_polygons"}}}}}