{"entities":{"Q2862205":{"pageid":2872925,"ns":120,"title":"Item:Q2862205","lastrevid":58034790,"modified":"2026-04-03T13:17:26Z","type":"item","id":"Q2862205","labels":{"en":{"language":"en","value":"The stretch factor of the Delaunay triangulation is less than 1.998"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6227054"}},"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":"Q2862205$0EB6BA6F-A146-4045-A68C-68F0E37EA84C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9a54a35e78ee029d2f8ded1578fcf74a29bc50f4","datavalue":{"value":"1302.65059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2862205$23E71D30-4727-4B9F-9683-599048307DE6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"39a527bbb3f6a4b62e069fa66d248ba2c2c3af1c","datavalue":{"value":"10.1137/110832458","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2862205$2FBD1A50-AE97-43E1-B0EC-CFB7FF18154B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"09037479074b394376ae3abcbf3130c1899f813a","datavalue":{"value":{"entity-type":"item","numeric-id":423935,"id":"Q423935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2862205$CECD739A-B550-4308-BE18-C8F6F23F354F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2862205$CBDF4324-946C-47CA-801E-BB422A86A4BD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"108246dca772a8e1d58c3ba11f0cdc16c904d0dc","datavalue":{"value":{"time":"+2013-11-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2862205$50F52F7B-2E42-45D2-B26A-7E63384112CA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"aa95ea1495680bf9dfdb5f13cdba76e427d4c541","datavalue":{"value":"https://arxiv.org/abs/1103.4361","type":"string"},"datatype":"url"},"type":"statement","id":"Q2862205$7A45917E-9A19-49F4-B8C9-6AF32F35704B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2862205$1EB23C23-9217-44C0-91E6-2503FE7C8D38","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"afd745756ef23812fca5d38e7dc4124cf89c6663","datavalue":{"value":"6227054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2862205$A7D6B804-53EE-4318-BA9E-AC67B5A2DC8F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5edfd6368999620c7e10cbba2e058c2b660abfd0","datavalue":{"value":"Delaunay triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2862205$626EC09B-C249-494F-8C38-406FD4863611","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34021ef787f4e28495d35f81de19ab2bcf2b70ec","datavalue":{"value":"stretch factor","type":"string"},"datatype":"string"},"type":"statement","id":"Q2862205$CB224F77-52C2-4BA7-8407-8437C8B0B7F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ada8d30f2ef08fc8cb2c5d1f7da969abbc27918a","datavalue":{"value":"dilation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2862205$269E4473-BD4E-494E-8F88-9DE3F9180575","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ad199608fdb9c69b55276f8bfa893b6b6a5aef4","datavalue":{"value":"spanning ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q2862205$533D5088-DF73-47B6-9F72-D2B8863A38FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf7d60f12fa0852907937b7d367162e8a586684","datavalue":{"value":"spanners","type":"string"},"datatype":"string"},"type":"statement","id":"Q2862205$08D42E5E-1E5C-4605-8CF4-76EDF14B6D45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q2862205$10CD92FB-A2C4-41A0-BE62-CD07ECB6F761","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":"Q2862205$2A8A31D6-3A18-4CBD-A32B-19B9C7296280","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"99bcc07ed851d64df7da93f81120643c87753f1c","datavalue":{"value":"W3103811994","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2862205$B847B495-F737-4C8F-AEAF-456D6117F8B8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bb0932499a2ac41b3d38abfab1b60615f6dae37d","datavalue":{"value":{"text":"The stretch factor of the Delaunay triangulation is less than 1.998","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2862205$92356300-4131-4B88-BB51-76D3836DD2D3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9778b09cd56d70dbff65ed1fa51392ed518a4fcf","datavalue":{"value":"Let \\(S\\) be a finite set of points in the Euclidean plane. Let \\(D\\) be a Delaunay triangulation of \\(S\\). The stretch factor (also known as dilation or spanning ratio) of \\(D\\) is the maximum ratio, among all points \\(p\\) and \\(q\\) in \\(S\\), of the shortest path distance from \\(p\\) to \\(q\\) in \\(D\\) over the Euclidean distance \\(||pq||\\). The problem of computing a tight bound on the stretch factor of the Delaunay triangulation has been an important open problem in computational geometry. In this paper, it is proved that the stretch factor of the Delaunay triangulation is less than \\(\\rho=1.998\\). This bound improves the current best upper bound of \\(2.42\\) (see [\\textit{J. M. Keil} and \\textit{C. A. Gutwin}, Algorithms and data structures, Proc. workshop WADS '89, Ottawa/Canada 1989, Lect. Notes Comput. Sci. 382, 47--56 (1989; Zbl 0766.52004)]). The bound obtained also improves the upper bound of the best stretch factor that can be achieved by a plane spanner of a Euclidean graph (the current best upper bound is \\(2\\)).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2862205$02BC675E-C0A9-4FE6-9D4D-F62659FCC261","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eabcaa4115c7d203cf999b1d6476a35edc125dbe","datavalue":{"value":{"entity-type":"item","numeric-id":256764,"id":"Q256764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2862205$B11F193E-0A3C-45ED-90F4-CD18F98416D9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"649d6e41a35828c2361a74e54f0077d00e549474","datavalue":{"value":{"entity-type":"item","numeric-id":5404432,"id":"Q5404432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6c822f6d2aa603151d4939d558fda24c8426cd1","datavalue":{"value":{"amount":"+0.9648866653442384","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":"Q2862205$2E0B0273-A7DB-4CBA-B95F-1865D2BDF8AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f85f4fb4f8831de87b8fd7ccd2e799f238a58653","datavalue":{"value":{"entity-type":"item","numeric-id":621926,"id":"Q621926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d13157320660a96365fc0c86f4dd1ffc4eda4b4d","datavalue":{"value":{"amount":"+0.9114878177642822","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":"Q2862205$690FFD6A-6C16-43AD-A9CB-44DFD6E80D89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6ca6634be19be1610be02b50caa9a19b1287a8c","datavalue":{"value":{"entity-type":"item","numeric-id":621930,"id":"Q621930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15a725005668e1c8c524d7d326b4c6d554ddc1bd","datavalue":{"value":{"amount":"+0.9092029333114624","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":"Q2862205$A17D9914-9CA8-4A25-8B05-F1B447FDFB5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"249b0a5b7e21822513d3b48f4cddf6e33e0a3fb0","datavalue":{"value":{"entity-type":"item","numeric-id":482347,"id":"Q482347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"026f37884efa6b509e3d3e71cac133147fdb27a9","datavalue":{"value":{"amount":"+0.8992124199867249","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":"Q2862205$9EB0CC42-2124-4DFD-94A7-DC80502A80FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4aed8f6eaf26aeec038c954a6a40d8b6e854cd80","datavalue":{"value":{"entity-type":"item","numeric-id":5077646,"id":"Q5077646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d499fda38a3485f5afb63d25266f79b036f190f1","datavalue":{"value":{"amount":"+0.895296037197113","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":"Q2862205$5F37B9CE-2C5D-4F94-BC15-234E57A999F9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2862205","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2862205"}}}}}