{"entities":{"Q5941092":{"pageid":8117894,"ns":120,"title":"Item:Q5941092","lastrevid":47657842,"modified":"2026-01-02T08:49:27Z","type":"item","id":"Q5941092","labels":{"en":{"language":"en","value":"Dynamically maintaining the widest \\(k\\)-dense corridor"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1635257"}},"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":"Q5941092$B8D52A72-FF66-4F0C-A778-6B177CA05BE0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"da04962a184e98d9dfbc41a56ecb72b2e8a91497","datavalue":{"value":{"text":"Dynamically maintaining the widest \\(k\\)-dense corridor","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5941092$EF1CCB51-2A0B-4101-9E59-5CA8E27500D5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"31c3b7937e45f28f0350aede3b51a050a0e437a8","datavalue":{"value":"0974.68218","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941092$4E5C052F-2357-4836-872B-41E2AE128C01","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"76a8d1e74a0b8c8285d549b56d64f325ff6158b7","datavalue":{"value":"10.1016/S0304-3975(00)00370-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941092$29C40378-F804-4A3F-9887-E1A4B0BD46B3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fc7009695144800ec158194ab275c08a49785642","datavalue":{"value":{"entity-type":"item","numeric-id":407526,"id":"Q407526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941092$E0987F7A-AFAE-46F8-9CC6-07BB237141A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0c84744ac09cc1b8afa9b5b879575eb75d92eee5","datavalue":{"value":{"entity-type":"item","numeric-id":1613421,"id":"Q1613421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941092$BCCC8F45-CCB0-414F-ADCA-234259D6E99E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca0f809e75b605da89222285942806748678a6ab","datavalue":{"value":{"entity-type":"item","numeric-id":390166,"id":"Q390166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941092$73A4C439-C354-4D2B-A35B-22F955F70266","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941092$C98F6676-C36C-49D2-B994-2A25DD41A563","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0d780905acb67c2b1b938af03e08b68df411214b","datavalue":{"value":{"time":"+2001-08-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5941092$FB407ACF-0EA2-4F55-82EA-A3C020A6A900","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4be7f08395929ba614bfff9a48cc20844ec6a7e2","datavalue":{"value":"In this paper, we propose an improved algorithm for dynamically maintaining the widest \\(k\\)-dense corridor as proposed in \\textit{C. S. Shin, S. Y. Shin} and \\textit{K. Y. Chwa} [Inform. Process. Lett. 68, No. 1, 25-31 (1998; Zbl 0925.68433)]. Our algorithm maintains a data structure of size \\(O(n^{2}),\\) where \\(n\\) is the number of points present on the floor at the current instant of time. For each insertion/deletion of points, the data structure can be updated in \\(O(n\\log n)\\) time, and the widest \\(k\\)-dense corridor in the updated environment can be reported in \\(O(kn+n\\log n)\\) time. Another interesting variation of this problem, called query problem, is also considered in this paper, where the objective is to report the widest \\(k\\)-dense corridor containing a given query point \\(q.\\) We propose two schemes for answering this query. In the first scheme, an \\(O(n^{2})\\) space data structure can answer this query in \\(O(nk)\\) time. In the second scheme, we construct an \\(O(nk)\\) space data structure afresh for each query, and then answer the query in \\(O(nk\\log(\\lfloor n/k\\rfloor))\\) time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941092$B58A47AD-8D42-4F41-B23C-C8416C032B33","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941092$D4D6C24C-B75F-4E4F-873C-542FF39DA908","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c5d7531323d9dda386c875e738879187636f81df","datavalue":{"value":"1635257","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941092$55FBA785-B1A6-49E1-9CD9-F438B4D34A51","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19c5d09b0b216c4028374d723d3005ad8f0f2587","datavalue":{"value":"geometric duality","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941092$8D54C348-647A-4ADD-9EAD-FF7FADAB5271","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d39571d6ac56dd086b1a820f29248dc61dff1660","datavalue":{"value":"levels of arrangement","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941092$A5CD4E40-3670-490C-8BF6-E412ECEA2FFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e42182f9836d59618892ab80aa4dfe152f83c4c9","datavalue":{"value":"corridors","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941092$3C8C7BA9-C778-4E66-A2EC-B595FD0B8880","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":"Q5941092$8B352DE1-ECCA-4422-AA0E-CEA6966DA4F6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c855bedbcde8f6ba6c8bdc8d30a598b9da36a6a","datavalue":{"value":{"entity-type":"item","numeric-id":4310578,"id":"Q4310578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941092$929A22E7-42C7-4000-8E4C-EC79C30CD8EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25b026e498c7466f890693e678f90760ff4b1c4e","datavalue":{"value":{"entity-type":"item","numeric-id":3772828,"id":"Q3772828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941092$7A5CDA14-31EC-4CCF-81DF-72FC9207B15F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941092$621B1894-526E-47BD-BC97-E56B65C0E5BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51b68e849556e001e66898f24a34ef6818ab4e6d","datavalue":{"value":{"entity-type":"item","numeric-id":1274672,"id":"Q1274672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941092$9BF822D5-6511-4D7D-8871-0D2A4B731259","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29ad1e89106c3c7d3f704040cc6d9d63795e72e7","datavalue":{"value":{"entity-type":"item","numeric-id":2728901,"id":"Q2728901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e77702f837b567de4e96061c324414ddeffc59e","datavalue":{"value":{"amount":"+0.9772525429725648","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":"Q5941092$8D174E1F-6C8F-4195-A798-0442ED522411","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c3f275769a91974bbabcb8de83acb7ac9b532d7","datavalue":{"value":{"entity-type":"item","numeric-id":3605487,"id":"Q3605487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bc1ac5e031e7efaddf4b73af469abfe1fdc13fb","datavalue":{"value":{"amount":"+0.7565085291862488","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":"Q5941092$E70DAD59-4451-4EAC-A7A3-9B7F9E1D7C71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5889cb5d16133c659e2b332e37e500b8389aec42","datavalue":{"value":{"entity-type":"item","numeric-id":989575,"id":"Q989575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5798be370712fd866f91c0f2a997b32129fed3eb","datavalue":{"value":{"amount":"+0.7557718753814697","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":"Q5941092$36C2D954-2ACB-4717-9D5E-5A52B7569DAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f450e36eb52047fc57cd3a89ee969031873b45a2","datavalue":{"value":{"entity-type":"item","numeric-id":844199,"id":"Q844199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"509c7aee067b8e575fad9339d19356dbb7a522dc","datavalue":{"value":{"amount":"+0.7537879347801208","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":"Q5941092$7BBE8F44-3719-4392-B470-608E170FE439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33c85bf35561f61a2a3b430401a910b9d9cf02c0","datavalue":{"value":{"entity-type":"item","numeric-id":1404528,"id":"Q1404528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5475e75353989a214ff64e7c09386c0d8398b4fd","datavalue":{"value":{"amount":"+0.7522594332695007","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":"Q5941092$26E74588-8E33-4197-8A04-B5FDD7448BA9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5941092","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5941092"}}}}}