{"entities":{"Q1095812":{"pageid":1106564,"ns":120,"title":"Item:Q1095812","lastrevid":69631287,"modified":"2026-04-13T08:20:01Z","type":"item","id":"Q1095812","labels":{"en":{"language":"en","value":"Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4029293"}},"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":"Q1095812$F2F6915E-8370-4C9B-BAA6-0F882C5BA2C6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"82add84afad7932feb55a065dc22af2aec2e0b7f","datavalue":{"value":{"text":"Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1095812$31D9C4F4-742B-4F32-924D-33618B0F86EA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f96a11dcd5fe78efbf7954796570514b3b38296b","datavalue":{"value":"0632.90080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095812$929A6269-6FE5-4E1E-9E38-3B70A8B40AFE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bf07966a558a69a839ac142c510f207e068d7b99","datavalue":{"value":"10.1016/0020-0190(87)90160-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095812$64752785-9652-417B-A115-C470EF6E1527","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a35b6403677dee48292ada35d89e01ed621942c7","datavalue":{"value":{"entity-type":"item","numeric-id":803160,"id":"Q803160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095812$DC43BEBA-8279-41F4-AD3D-B006A4F583CA","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":"Q1095812$3E9A99B6-DDFB-4954-A357-69A1B1F82F05","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":"Q1095812$F5BB9DD9-C567-466C-88C8-795AB0DE4C86","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bd78149c773002d2127dd16e029479db5361c20d","datavalue":{"value":"A traveling salesman cycle for a set S of sites in the Euclidean plane is a closed path of minimum total length that visits each site in S exactly once. A triangulation of S is a plane graph with the sites in S as its vertices and the sum of the lengths of all edges as its weight, and for which every region interior to the convex hull is a triangle. The Dulaunay triangulation of S, DT(S), is the graph whose vertices are the sites S with two sites \\(s_ 1\\) and \\(s_ 2\\) adjacent if \\(V(s_ 1)\\) and \\(V(s_ 2)\\) share a boundary consisting of more than one point, where V(s) is the set of points closer to s than to any other site. If no more than three V(s)'s meet at any point, DT(S) is said to be nondegenerate.    By exhibiting an example, \\(S=(4,6)\\), (0,0), (5,0), (11,1,0.1), (9,2), (7,2), (6,10), this paper shows that DT(S) does not necessarily contain a traveling salesman cycle for S, even if DT(S) is nondegenerate and Hamiltonian, nor does a minimum weight triangulation.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095812$D5862CC2-21F4-4F78-B6A7-FCB8D6154EEF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095812$4D5F99E0-A2F7-4ED4-8E3E-35FD70BFDA87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095812$20A96B8F-5845-46D4-AF7F-6D5B154D2867","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"22cc6973b8e4e7dd06cce35fc67636f13591f5a6","datavalue":{"value":"4029293","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095812$7CDA94F3-94CF-4265-9D23-C827E29E5376","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095812$4987D9C5-F7D2-48EB-957D-B4EE45C1EA13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc7b4d2c7ddddbdcaefa50a42c56e156daf5fead","datavalue":{"value":"Hamiltonian graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095812$4D13DB34-7743-4636-B375-0301FD71B3CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef75e6cadb836ddc74d2cc7066e9b6cb18e87f38","datavalue":{"value":"minimum weight triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095812$6B936274-5A07-4906-86AB-2A3D89F01362","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d975c8e13006fbe9b4f6c347ea88f3b06e6e4c7","datavalue":{"value":"Voronoi diagram","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095812$028EE4D9-5D74-49D2-9CBF-729A74666060","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"558157e67b39cc776ee331ec4d8ec056199610b9","datavalue":{"value":"traveling salesman cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095812$BFA592AC-2AE1-4383-B446-0CC6FBF1BF48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6f129b371148b50d4157706aa438ce0d7329c304","datavalue":{"value":"Dulaunay triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095812$55A3D8C0-A7C9-402F-A98F-511EA7AF02A0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5227faecbb85554f67462af138161eaf1403cae2","datavalue":{"value":{"entity-type":"item","numeric-id":1862807,"id":"Q1862807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095812$900B0BD2-D0D0-4AA7-BFCD-02638D002391","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":"Q1095812$1CE0AA66-29F8-432F-8B88-9A8FF81CD810","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7989e4aa8df45322b83d9ab8b6ab7524cc216fa8","datavalue":{"value":"https://doi.org/10.1016/0020-0190(87)90160-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1095812$12273C11-92E8-4B14-BD94-427E480A7EEA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"92dcf1242fd3d2d1dbf23b7cf6086b16c1359215","datavalue":{"value":"W2050895339","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095812$5DDB915A-4933-42AB-BE7B-A7A299831932","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a74668e077023b019771a1a7d5a132cfdf00221","datavalue":{"value":{"entity-type":"item","numeric-id":1055435,"id":"Q1055435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095812$28DAAAE4-DB84-4582-9C88-D59D43222029","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694910451200ab7067ebbccacf142af3ac2a2369","datavalue":{"value":{"entity-type":"item","numeric-id":3992847,"id":"Q3992847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095812$C0D08DCF-356D-4094-82C2-23CF2B57B440","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"178c6cf49c659567ba5127140e4fdefd823209f8","datavalue":{"value":{"entity-type":"item","numeric-id":2384914,"id":"Q2384914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2be50020da44f4f53abe6aeebbb06b677ee1c3f5","datavalue":{"value":{"amount":"+0.7888751029968262","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":"Q1095812$7346E96E-1C4B-48A0-A003-3A51FF2CEAA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f58a5039ab33ef3639ab83f001a1c018055102f2","datavalue":{"value":{"entity-type":"item","numeric-id":1343467,"id":"Q1343467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab33e546931601bc26962d59191150259dd0f993","datavalue":{"value":{"amount":"+0.7493857741355896","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":"Q1095812$AB5F8FB8-CC02-4A93-9DB2-F13F50830468","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f4142bd5117020d9be2f6073ef9e6e1e078e22f","datavalue":{"value":{"entity-type":"item","numeric-id":803161,"id":"Q803161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6819af764b37f9d615f5c4cd8b2a58e9fed47a8","datavalue":{"value":{"amount":"+0.7488343715667725","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":"Q1095812$9859EAA4-B5A9-45CA-84DF-913A0C4CE81A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2dcd33d7f98fa7673f8be31f9aeec347e7bcbcd","datavalue":{"value":{"entity-type":"item","numeric-id":1917249,"id":"Q1917249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7110d5f97a96b011e1e4d2d1dff02f40af1cf3e","datavalue":{"value":{"amount":"+0.7352461814880371","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":"Q1095812$4DD5B550-AEE8-4D00-9898-7AB7B35DC88C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d2311a74c8ed5c7ee2d66a6548c6d82b5d13ce3","datavalue":{"value":{"entity-type":"item","numeric-id":4028874,"id":"Q4028874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e66cced5f3f480c2270602a03b6445636005d6b","datavalue":{"value":{"amount":"+0.7295564413070679","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":"Q1095812$04C0D422-0DC0-4CF7-8C42-D795CE26A6E8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Traveling_salesman_cycles_are_not_always_subgraphs_of_Delaunay_triangulations_or_of_minimum_weight_triangulations"}}}}}