{"entities":{"Q1108000":{"pageid":1118749,"ns":120,"title":"Item:Q1108000","lastrevid":69659934,"modified":"2026-04-13T08:31:46Z","type":"item","id":"Q1108000","labels":{"en":{"language":"en","value":"Time-and space-optimal contour computation for a set of rectangles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4066326"}},"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":"Q1108000$E11FDB31-C5D4-42D1-98B1-E8BB95709992","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ae5efed3a073353958656a2fe8f01009699f3ba0","datavalue":{"value":{"text":"Time-and space-optimal contour computation for a set of rectangles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1108000$1970BB41-8A9E-40D4-A5EF-F0B75A8B82D2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9212e11d3d0f73feb226bbcffa6258fcb1d24582","datavalue":{"value":"0653.68032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108000$0A43D370-A171-42DC-8224-7F78FBDE44DD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fcde2a123974c248c37d1a089ac9a0a1a74dd986","datavalue":{"value":"10.1016/0020-0190(87)90159-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108000$0AE47D36-BA84-4BE5-87A9-283294D149CE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0327d5313d734dde2c609f96abfb0c99d20abfac","datavalue":{"value":{"entity-type":"item","numeric-id":539451,"id":"Q539451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108000$8351B2FE-8898-4C41-A486-485EB76948DE","rank":"normal"},{"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":"Q1108000$8ABA48BA-C88E-4C87-B6B0-AFB291B06DAB","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":"Q1108000$09625496-D3EC-45A3-9D1E-68369A3C9006","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":"Q1108000$D9A5FA76-2D42-4223-9102-84BB741DB04C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"245a7be787f16a860ba0c2f8ea059a8a9943ad57","datavalue":{"value":"We present the first time- and space-optimal algorithm for the problem of computing the contours of the disjoint polygons defined by the union of n rectangles in the plane. It requires O(n log n\\(+e)\\) time and O(n) space, where e is the total number of edges in the contour cycles. The space optimality of the solution is demonstrated by way of a combinatorial argument.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108000$64BD6773-F559-41BD-9FBB-4E9DCF758270","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108000$46507039-EA8D-41B2-A44B-49480F35C610","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa4669cf5eaa224b5d3554d9705827ca09f43afb","datavalue":{"value":"52A37","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108000$A841FE6E-5F05-4045-BC73-34ECF4D11612","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"54cac70b4cba65c3f0c77e00e54a076f51de38e2","datavalue":{"value":"4066326","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108000$AC57B713-6687-43AB-B34F-3E00D091ECC3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d2b6c8496f82176604a3267a071e03fc761b948","datavalue":{"value":"optimal contour computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108000$6E43B49A-6E4F-498E-87BC-4D16875F98DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108000$C39D0868-A639-4333-80F3-9A9F6E2ECC2E","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":"Q1108000$A2E87C1D-C7A8-4778-B6F5-8EDD69235EC0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"de9550a7aa04e52c93398e2c40433b7a4853c92e","datavalue":{"value":"https://doi.org/10.1016/0020-0190(87)90159-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1108000$EB897F8E-591D-4274-94D8-DEB1411D0062","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2fada48485bdc5b5889b12c64c46a973bb0eef85","datavalue":{"value":"W2001773778","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108000$71E49BF1-928A-4234-861A-1148691EF7FE","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":"Q1108000$995D19F8-3522-451B-9BDE-83638A7D7A08","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":"Q1108000$FD924F3A-9EFA-45C6-877B-D2966D3593E2","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":"Q1108000$941AA161-936B-4B6A-9B94-FD8B07C76992","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a424f44a8dbc665539390a6f9c8785edbdbed5f3","datavalue":{"value":{"entity-type":"item","numeric-id":3953198,"id":"Q3953198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108000$E915B539-DFE9-4A44-8586-FE8AABFAB6E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d63785a8df4bed3fd947676c908f3b67c8685e7","datavalue":{"value":{"entity-type":"item","numeric-id":3685221,"id":"Q3685221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108000$238746A0-959E-4455-B981-96373AFFDDA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fba2285769742dd3f9f65fff1612d0107b4a7be5","datavalue":{"value":{"entity-type":"item","numeric-id":802313,"id":"Q802313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108000$D4F2AB5C-0B0A-4052-BF06-9F5B4DC63C21","rank":"normal"}],"P1643":[{"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":"1b0a23f886df10734042aed2cb5d1cb3d9aab765","datavalue":{"value":{"amount":"+0.91680246591568","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":"Q1108000$99378B2F-A996-4563-ABB6-105A61542C72","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":"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":"Q1108000$3C8A2ADC-CE71-4F7D-920B-335DB57910A1","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":"5a594e8b17a15a3160835ef4e859ad9f8d87816b","datavalue":{"value":{"amount":"+0.823540449142456","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":"Q1108000$DF112F05-508E-4245-813D-5C7BF988DD47","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":"9e89d5ec57af098afb75589b86ea5cff54f8f517","datavalue":{"value":{"amount":"+0.8133637309074402","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":"Q1108000$EEC565FE-E188-42D3-BB70-C0F6675C491A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f811dec03a3157469e4540cbedc7cd587c10dcab","datavalue":{"value":{"entity-type":"item","numeric-id":1943607,"id":"Q1943607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e7350fb27c3d47c7abdb910bd0440fcdb1ed27a","datavalue":{"value":{"amount":"+0.8101411461830139","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":"Q1108000$341B7C17-39FF-4062-BCCD-4A0F9D5B1DE1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Time-and space-optimal contour computation for a set of rectangles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Time-and_space-optimal_contour_computation_for_a_set_of_rectangles"}}}}}