{"entities":{"Q1094871":{"pageid":1105623,"ns":120,"title":"Item:Q1094871","lastrevid":66712077,"modified":"2026-04-12T12:19:20Z","type":"item","id":"Q1094871","labels":{"en":{"language":"en","value":"Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4026828"}},"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":"Q1094871$C45B3E54-8206-45E4-A52A-6D5E79561D0E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f6f829afbc842cfe0bbd4b464606e1f4f72f55b4","datavalue":{"value":{"text":"Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1094871$F694F643-4B15-49B9-96F7-262736CDCC50","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d13cdeb82692016362cb45b7e13af124ef189813","datavalue":{"value":"0631.68042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094871$CB1811AC-C620-4710-AF2C-5FBCAA4C2A8A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"50b555959d5aafb51dbdc460197d80a28557b992","datavalue":{"value":"10.1007/BF01840348","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094871$AC37E5C9-C2F4-48D1-AD42-5CA927B51B64","rank":"normal"}],"P16":[{"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":"Q1094871$C0F78727-FCA7-4F7F-9C7D-CA8C5F67D4AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aed274e58471806e973e3926af8e50abb8242477","datavalue":{"value":{"entity-type":"item","numeric-id":1162143,"id":"Q1162143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094871$7B7652DA-4D26-4F46-8C94-D5837CF549E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d871c1b75fb83a30076e692713ffd500de027eb4","datavalue":{"value":{"entity-type":"item","numeric-id":676576,"id":"Q676576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094871$79169DDE-F5F6-4CAD-9EE9-C64A815299F5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094871$AD57B442-457D-4D10-848A-1E10A070FBA9","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":"Q1094871$6729E97F-7016-422E-A4BE-F6B1FD60ADD7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"075a01e86a3184be79e29fef7bd384e29689ec4f","datavalue":{"value":"[For part I of this paper see Commun. Pure Appl. Math. 39, 423-483 (1986; Zbl 0601.51025.]    The paper discusses the construction of a generalized Voronoi diagram for two-dimensional space of n lines and vertices. It is shown that the size of the Voronoi diagram is \\(O(n^ 2 \\alpha (n)^{O(\\alpha (n)^ s)})\\) for some fixed integer s, where \\(\\alpha\\) (n) is the inverse of Ackermann's function. Also shown in the paper is the construction of this Voronoi diagram in time \\(O(n^ 2 \\log n \\alpha (n)^{O(\\alpha (n)^ s)})\\). The results are obtained by case analysis of the vertices in the Voronoi diagram.    This generalized Voronoi diagram can be used for a motion-planning algorithm for the ladder-moving problem in a two-dimensional space with polygonal barriers consisting with the same time complexity. Recently, there is a combinatorial result by \\textit{P. Agarwal}, \\textit{M. Sharir}, and \\textit{P. Shor}, ``Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences'', which implicitly improves the bound given in this paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094871$069CDF22-060A-4A63-BB21-AF01714BB9B5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094871$5AAEC6C7-8580-4AEC-B629-03D222D6F0C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ddd8cb1932c6bc41681458db5f685a2a286fde55","datavalue":{"value":"52Bxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094871$2E6AB767-2B27-4E1A-AD9D-3E1A3B43EB03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa4669cf5eaa224b5d3554d9705827ca09f43afb","datavalue":{"value":"52A37","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094871$80BAE841-5FEA-4942-957A-9B4E24E4B3BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5ae9e2988e76d371f7e87b79bcd004ea2b80f64","datavalue":{"value":"51M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094871$5DE9FCD9-17DA-4585-AA48-6CFF5521B7FF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"453a41af7466d224f53c9ba7f96e2915cd249b1f","datavalue":{"value":"4026828","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094871$8D10158E-BA95-408A-B3B1-D272C1365D42","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094871$B11DC60B-A764-4138-9CD1-9DB71A1FA451","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"baa401a90f7be40837e492046fd0146ae8e354d2","datavalue":{"value":"robotics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094871$01FF9A71-694B-4A73-B664-77835993DCE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cbda80faf7c66fe809412afa8394210863f0c0a9","datavalue":{"value":"configuration space","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094871$EFC204B9-7051-45B8-A8BD-F804D6C287C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d961e6d08b938486a61f05078d3ad494aa0f847c","datavalue":{"value":"generalized Voronoi diagram","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094871$9DB34828-682E-4F4D-8A9E-A671750923F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eee73798528c6fe04f254fcf3e3007e5cd5474fb","datavalue":{"value":"motion-planning algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094871$230A7B0D-FD69-4EC2-9E61-F02731654B63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a78c76a6ee72bcfb0c608bac57d4bb852516c3c","datavalue":{"value":"ladder-moving problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094871$9D9985C2-2E1F-4FC1-95E9-A8AAD3416F0D","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":"Q1094871$3CD4E163-62F8-49B2-BABE-153011C88156","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a242496d908b6d1e30e137bd48db323e9a6e17e","datavalue":{"value":{"entity-type":"item","numeric-id":5340927,"id":"Q5340927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094871$9E3C979A-4B3F-407E-88E5-92701E882FB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7f962d4b7bceadb914a43cc05d640fec4e9860f","datavalue":{"value":{"entity-type":"item","numeric-id":5619850,"id":"Q5619850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094871$D951D9B5-1513-4E5B-A234-C050A18ED87B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c368a550cf5b4e92a6d4f0e58d9ca1eb20b223cd","datavalue":{"value":{"entity-type":"item","numeric-id":1097884,"id":"Q1097884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094871$6A23FB0C-1AB9-45A8-A5AB-31ED09A80CD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d00fee834e0792b465974b4a515e53fab6ed19d9","datavalue":{"value":{"entity-type":"item","numeric-id":3219802,"id":"Q3219802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094871$8922A74F-67D8-490A-B28D-7A9D948E7435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f3a00c41c8365dadba43270184930d03ceda008","datavalue":{"value":{"entity-type":"item","numeric-id":3217189,"id":"Q3217189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094871$FB3F8DE7-2256-40AB-9CD9-6F06320A029A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8332468c56cf425ddf859080eb3b69a9207db47c","datavalue":{"value":{"entity-type":"item","numeric-id":760006,"id":"Q760006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094871$078A241A-E773-4E29-BDD3-37C1E89F1D44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3be39f64690d4cb3f58df35a467dec31b3420776","datavalue":{"value":{"entity-type":"item","numeric-id":1097885,"id":"Q1097885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094871$56FA96D7-3444-460E-A086-59A03C549C42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de292e32a27b4a9a5a47973907ab27caf0155dfe","datavalue":{"value":{"entity-type":"item","numeric-id":4041583,"id":"Q4041583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094871$7E5DF345-240D-4C65-B4E6-78586FD4DCAC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"681ff2593ecac5f579129df906842a037e90a2b2","datavalue":{"value":"https://doi.org/10.1007/bf01840348","type":"string"},"datatype":"url"},"type":"statement","id":"Q1094871$7B43F844-F773-4801-8A7D-CD24EFAF7D35","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e6b4ca3b1e03eb241d6009390f102d3b53e142e3","datavalue":{"value":"W2025475855","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094871$A39ACE00-B34B-404B-84DC-85DCA55CC7AD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5ef37e927cd945054fdec13852b418cd4cd1089","datavalue":{"value":{"entity-type":"item","numeric-id":3736451,"id":"Q3736451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be7cbf6a09244621f7945c716c747e4e7c072bc0","datavalue":{"value":{"amount":"+0.90426147","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094871$3F24CC7F-A71A-4A6A-BF26-A99FF127E386","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca7b67631e7df3f22a4619e56d08d57a4a00a1b5","datavalue":{"value":{"entity-type":"item","numeric-id":4201933,"id":"Q4201933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0654a92ac0be990757b1476291a0a69de7b47c20","datavalue":{"value":{"amount":"+0.8858963","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094871$E5BC0A46-774D-4CDD-89BB-F77F111D9C1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ee2d14938fdeb4fc12dd51877c359540ef6bf0f","datavalue":{"value":{"entity-type":"item","numeric-id":3824965,"id":"Q3824965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1bfac688ea710f4b5d78bdbc3f2dafdb1035ead","datavalue":{"value":{"amount":"+0.88098323","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094871$7B3A5A3D-2C2F-4CD0-B67D-28393DF6DBAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2089bfd6eadac3eb1fbac8f7c8c2a4945c216635","datavalue":{"value":{"entity-type":"item","numeric-id":757052,"id":"Q757052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e47d346a5ebb8c250b854e8f185887be3036c154","datavalue":{"value":{"amount":"+0.8767387","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094871$1BFA64C9-F65A-4728-AD1B-6D3606A1D1F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39bb06b43bbbe889823ff74cfaa7dd971d8c9522","datavalue":{"value":{"entity-type":"item","numeric-id":4559053,"id":"Q4559053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae1da1767206c1452842e2abd5eb6cc5b72ee100","datavalue":{"value":{"amount":"+0.87468135","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094871$2A2FB609-F9AD-4B23-A04F-EE373A3C25BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4bd8bfad7007029159e3df05d6219fb1f703b57","datavalue":{"value":{"entity-type":"item","numeric-id":3975933,"id":"Q3975933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c656d11f58be2bea5e7f6880dc8242fbe439ea2f","datavalue":{"value":{"amount":"+0.8725562","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094871$51D9DF79-7230-48B8-BEFA-E9280922111F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ba55620fb5756dc154c1448d6feae28e04fcb77","datavalue":{"value":{"entity-type":"item","numeric-id":3518549,"id":"Q3518549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b71b9af01a64e12b3dab7ef1b6a59ec3a1a6d360","datavalue":{"value":{"amount":"+0.87063754","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094871$24439CC8-B749-49AE-8B8C-69E352D52655","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5978f3330f9daaea156dc3ce162bded3e150e7ce","datavalue":{"value":{"entity-type":"item","numeric-id":3132855,"id":"Q3132855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc62e797b437500166d0c677a2d7fecd8d3637aa","datavalue":{"value":{"amount":"+0.8663364","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094871$828FD140-1A56-4467-A181-524160E48012","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"905f3c3ed28400460b0df5f5bb89b938e5997a60","datavalue":{"value":{"entity-type":"item","numeric-id":2414862,"id":"Q2414862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc62e797b437500166d0c677a2d7fecd8d3637aa","datavalue":{"value":{"amount":"+0.8663364","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094871$3D5EFDF2-A630-40A4-895B-26FE0831EC26","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Generalized_Voronoi_diagrams_for_a_ladder._II:_Efficient_construction_of_the_diagram"}}}}}