{"entities":{"Q3973054":{"pageid":6002953,"ns":120,"title":"Item:Q3973054","lastrevid":108491423,"modified":"2026-11-06T17:03:27Z","type":"item","id":"Q3973054","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 16400"}},"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":"Q3973054$D46B7CAD-F18F-4C63-8629-D0796487B59C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2ae4a33232bbcd562d6d68a5f4b031bba506f376","datavalue":{"value":"0744.90071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3973054$98E98049-B155-4117-BE82-998948919EC6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"34f917cdeb4bd9133df4fa785ce88cb684acb40a","datavalue":{"value":{"entity-type":"item","numeric-id":3795796,"id":"Q3795796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3973054$69C6656E-40A2-4683-A91C-2CB7E17E5615","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3973054$021EC5E6-813A-46AD-A16A-4D3320AA2987","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3973054$9BF82CC5-09AE-4D5B-B059-9B061EDDC98B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3973054$DC07AA16-6A33-4086-A855-C18639E423A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3973054$35F8BF7D-B766-4E58-B113-EE36D6D3A614","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3a79006351040796a1c131c951f30dea25998347","datavalue":{"value":"16400","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3973054$3362A80A-695A-4D0E-B051-933D8E72D80A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d975c8e13006fbe9b4f6c347ea88f3b06e6e4c7","datavalue":{"value":"Voronoi diagram","type":"string"},"datatype":"string"},"type":"statement","id":"Q3973054$11818C3E-7671-4479-AB94-00F37E95933A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1bc5c0133c7c983c1d11e1ede27f71a471633b5","datavalue":{"value":"Euclidean traveling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q3973054$622D9C81-1BBD-4DED-9580-1ABB8E734264","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f7c2f3425e2fe7ac6723999eddcd5f45b371566","datavalue":{"value":"elliptic length of the perturbation","type":"string"},"datatype":"string"},"type":"statement","id":"Q3973054$6850DD21-C6EA-43AE-844A-D130411E27D1","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":"Q3973054$16E7016C-F507-4D62-BDBB-63A045A2EED1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ddb878304865d882046c7579a5026ae6bdda1eb","datavalue":{"value":{"entity-type":"item","numeric-id":1392940,"id":"Q1392940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15539388725d9f1e2719ffff64f5e685a30efa18","datavalue":{"value":{"amount":"+0.8470753","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":"Q3973054$A982DE54-98CD-4871-8A65-43B7B9F1D764","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd1e6564d037d845089390ebdeb422cd2ff84cc1","datavalue":{"value":{"entity-type":"item","numeric-id":3113753,"id":"Q3113753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"253551891d5417ad36ef7e6f0a5f9a3b1fc4f33b","datavalue":{"value":{"amount":"+0.84042233","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":"Q3973054$FAD2BFD0-9183-4A4F-B866-B91264C07155","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3665a25551e0af0446c7f06fb1184fc6040db49","datavalue":{"value":{"entity-type":"item","numeric-id":2806910,"id":"Q2806910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"916b8f532ad09ed20d222f0d363d4bdfafcbaea5","datavalue":{"value":{"amount":"+0.8360599","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":"Q3973054$0DC1AA42-0075-4933-BFA6-2686FAC13F69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"621cc13463e4b5891e04aafc74076bde18653525","datavalue":{"value":{"entity-type":"item","numeric-id":4842128,"id":"Q4842128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c83fe1819c2e495da773e88fc46110f765952b4d","datavalue":{"value":{"amount":"+0.8240257","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":"Q3973054$D7890C0E-0770-4F25-86B2-89396348AA6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a542a83aa4861169d6451de8138758dc2607f9a8","datavalue":{"value":{"entity-type":"item","numeric-id":5470167,"id":"Q5470167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2f3b40e609fd913d2d0d983da099b444c86ac69","datavalue":{"value":{"amount":"+0.8228773","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":"Q3973054$ACDD4002-5AC1-48FF-9541-6DA1A95639EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35dab3476d0a583d04e7291d50418e455ab0b8b2","datavalue":{"value":{"entity-type":"item","numeric-id":834186,"id":"Q834186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b89064cf92c72fe83f269a602f6758032f778a7","datavalue":{"value":{"amount":"+0.8223983","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":"Q3973054$BD141EB2-0159-4962-8BFD-F881F514474C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"303230dda06b4d9388b561d7a42bce704910b7e0","datavalue":{"value":{"entity-type":"item","numeric-id":1111946,"id":"Q1111946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b5cbfe3b1ba3e9357cdeb1b3944dd9f91a0c2f2","datavalue":{"value":{"amount":"+0.8219936","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":"Q3973054$BF2E9694-4B16-4C93-A77F-72AB2004FC59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"812a7c993d0094320676072890d30bb1dcef26c3","datavalue":{"value":{"entity-type":"item","numeric-id":5712102,"id":"Q5712102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1080aee4f6144d64cdcdbe2af04c430f2b476382","datavalue":{"value":{"amount":"+0.8212601","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":"Q3973054$C25542B8-8985-4590-88E0-9F9F10010E98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2aacaff91a6c9c0e673a85212993b3ed782cb93c","datavalue":{"value":{"entity-type":"item","numeric-id":2103946,"id":"Q2103946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d14286063660ac78f939eb28a0621f3c6e6428c7","datavalue":{"value":{"amount":"+0.8206758","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":"Q3973054$3A8ED7F0-73F1-4320-827E-34AB3AE2BFC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36e5f9e1efd79594403dbb611f72c9f625ccd139","datavalue":{"value":{"entity-type":"item","numeric-id":3158519,"id":"Q3158519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3fb9a2ee5f6e88256c9d766b52de209fb5dfe21","datavalue":{"value":{"amount":"+0.8198476","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":"Q3973054$1B74989B-B9E9-47C3-ADED-4A103F4E115D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b2e4ac38a35fdeaa45b6c73d1ffdb5884b34d6f3","datavalue":{"value":"[For the entire collection see Zbl 0722.00036.] From the author's abstract: ``It is shown that the Voronoi diagram for the Euclidean traveling salesman problem is piecemeal quartic and hyperbolic. The shortest tour is treated as the union of a set of perturbations of the convex hull, with interior cities added incrementally, one at a time. A perturbation is defined to be the union of a new city with a subpath which connects two adjacent hull vertices to a set of previously entered interior cities. The length of a perturbation is therefore equal to the sum of two variable distances, minus the sum of a set of fixed distances. This length is called the elliptic length of the perturbation. Beginning with the convex hull, a single city is randomly added to the interior, and the hull is perturbed to capture the new city in optimal fashion. For a perturbation of a specific elliptic length, this quantity determines an ellipse symmetric about a hull segment, with foci at the segment endpoints. Any other hull perturbation of the same length defines another ellipse symmetric about some other hull segment. As the perturbation length is about to vary continuously from zero to infinity, a set of confocal ellipses is produced about each hull segment, and the intersection across all other such sets produces a set of quantics. For the special case in which hull segments share an endpoint (focus), the locus is a hyperbola. Each hull segment is bounded by those quartics for which the segment is the source of minimal perturbation length. The region of the plane thus bounded is called the quartic Voronoi cell for that segment. The quartic Voronoi diagram is shown to differ from the traditional Voronoi diagram in three distinct ways: it depicts shortest tour connectivity rather than point-to-point proximity; its cell boundaries are quartic and hyperbolic rather than linear; and the diagram is bounded by the convex hull rather than being unbounded. A naively derived ceiling function demonstrates that an unsupervised perturbation approach is of exponential complexity, with a scaling factor as a function of the size of the hull. By resorting to an algorithm which exploits the canonical forms, it is shown that this bound may be diminished to \\(O(n^ 3)\\)''.","type":"string"},"datatype":"string"},"type":"statement","id":"Q3973054$C1288B68-78C2-432A-BF46-BB27C01A2F9B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3973054","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3973054"}}}}}