{"entities":{"Q1186079":{"pageid":1196828,"ns":120,"title":"Item:Q1186079","lastrevid":66795033,"modified":"2026-04-12T12:54:32Z","type":"item","id":"Q1186079","labels":{"en":{"language":"en","value":"Classes of graphs which approximate the complete Euclidean graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 36174"}},"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":"Q1186079$652B9CC7-FE15-414A-8338-93DCA57624BD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e388d13a09757f9bd78dbef201f8353d2a456565","datavalue":{"value":{"text":"Classes of graphs which approximate the complete Euclidean graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1186079$D49F3051-5BB0-4E09-AF88-D0125BB092C3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"373606c8ca7582d2eae6974b5bc161a7e8fcf00d","datavalue":{"value":"0751.52004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186079$6ED6D5EA-2657-41D6-8805-066A2B8E1548","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bac30a365774b65bc44efa532066548e9faf165b","datavalue":{"value":"10.1007/BF02187821","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186079$150646EA-E47D-4890-A191-FA15FADDB19A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"725145adf60736a410a92f7f2d72d3094c36ae9d","datavalue":{"value":{"entity-type":"item","numeric-id":680147,"id":"Q680147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186079$257F2B31-577E-4027-82F9-FCBDDE976B48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a60531c6793850158b3bffca152494c33aad363c","datavalue":{"value":{"entity-type":"item","numeric-id":1186078,"id":"Q1186078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186079$B717BC26-2487-45E1-B6DE-8137FF6D6970","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186079$BC69CA5B-DABC-4DE4-91AE-3F8970C9994D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1186079$7497B578-287E-4CEC-8085-79C0907E0489","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3476bbdf3b065cf1e4eb7e9601f0568ec48cf4ac","datavalue":{"value":"https://eudml.org/doc/131177","type":"string"},"datatype":"url"},"type":"statement","id":"Q1186079$2DB81938-C2D8-4C7F-92BA-A46E0D1F207E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1b39e2b986e3944684bdf2d79774f900f73fd915","datavalue":{"value":"A euclidean graph is a graph with points of the plane as vertices and edge-lengths the euclidean distance between the endpoints. An euclidean graph \\(G\\) \\(t\\)-approximates the complete euclidean graph (t-ACEG) if for any pair of vertices the shortest path length in \\(G\\) is within \\(t\\) times their euclidean distance.   In this paper it is first shown that the graph corresponding to the Delaunay triangulation (dual to the Voronoi diagram) is \\(2\\pi/3\\cos(\\pi/6)\\) \\((\\approx 2,42)\\) -ACEG. An example is known for which this graph is \\(\\pi/2\\approx 1.57\\).   The authors then define a new class of euclidean graphs, the fixed angle \\(\\Theta\\)-graphs, for any \\(\\Theta=2\\pi/k\\) \\((k>8)\\), which are \\(1/(\\cos \\Theta-\\sin \\Theta)\\)-ACEG (e.g. for \\(k=40\\) we have \\(\\pm 1.20\\)). The interest is that this bound decreases with increasing \\(k\\) and that the corresponding \\(\\Theta\\)-graph may be constructed for any fixed \\(k\\) in \\(0(n\\log n)\\) time (\\(n\\)=number of vertices) by a plane sweep algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186079$96E28D54-1A6F-491B-AAC5-82A07DBF9EAD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"78931806833c54190437f3675cf624ba3d256107","datavalue":{"value":"52B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186079$AE9CD8BB-DC0E-4AB9-BD74-32FF944A213D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186079$586C5BB6-C2FE-4EC9-A8F2-54521A78E0B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186079$931B5F43-A2D4-4DFF-8BE6-7A44A593F63F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b143b79160ecbd84018a9432f7528f4f2e56eb50","datavalue":{"value":"51M04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186079$8B72D596-BB08-4E4E-9163-DAAD8C9B0505","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186079$72E87682-E5B3-4998-9E70-B3521CDB6879","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"eb9a27b57b9a6db7344507f650d97795c70ef3ec","datavalue":{"value":"36174","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186079$251125F5-D9E4-4943-9FC7-289137CF7F79","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b07592d56ecf568b9be312d33a2a1b32a6f3100","datavalue":{"value":"euclidean graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186079$ED6ACB47-0FAE-40E0-8ED1-4FB3B39DDEA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc058f54aac0023b7543c366366b86bc4e72c56b","datavalue":{"value":"approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186079$444E9218-25DB-4F6A-AE62-090F2AFBDFF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b02361b053584e64560290645849ffa26160a7b","datavalue":{"value":"Delaunay-triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186079$A1839877-61B7-4989-B679-6CBFCF05CB41","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"b21214294af11eb224785b88c8e19be1132737f6","datavalue":{"value":"Q56047089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186079$AD113A81-0FAD-4EA1-920C-CA4889D56A8D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5e09f3da1a7483864918926ab5885138a8f45aaa","datavalue":{"value":{"entity-type":"item","numeric-id":166210,"id":"Q166210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186079$B3F6E7C3-CB07-4F6D-9B56-047FB322A854","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":"Q1186079$18C472A1-C014-4892-A334-465E5EBD5837","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"39fa97f896f800ee47e86b3480a93293f8b1f158","datavalue":{"value":{"entity-type":"item","numeric-id":5581251,"id":"Q5581251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186079$BB6602B6-C3AC-4CE4-B480-3AFCB8414E0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a7d12ad715ea384e4f5dfa32c3b1f65fa44d396","datavalue":{"value":{"entity-type":"item","numeric-id":1823959,"id":"Q1823959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186079$CB6F6B72-D5AF-4E9D-A690-45CAC9BC3D57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ffc7c8b334d26c0686dd1a9b8ac5d7d5836aced","datavalue":{"value":{"entity-type":"item","numeric-id":584279,"id":"Q584279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186079$FA5FEE52-0831-4D38-B73A-233D920A7041","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd94578b97c83ef7077e73a3f78c579ae10dd88b","datavalue":{"value":{"entity-type":"item","numeric-id":3826599,"id":"Q3826599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186079$8E665E3E-B06F-4D09-9E19-D9C389D45FAA","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":"Q1186079$42A80375-DE98-4535-B121-365E536B2795","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"970d948eb029eca34ea06daddb9b60913ddb8101","datavalue":{"value":{"entity-type":"item","numeric-id":1087335,"id":"Q1087335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186079$0DBA1ADB-A534-4ED0-8AA3-DFA09D07D2AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a49d6af7b2df96ccb57b811f981edcbee6fa50fc","datavalue":{"value":{"entity-type":"item","numeric-id":3954830,"id":"Q3954830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186079$6FBE518F-4D00-4958-A8D1-D09A715234DD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12cd9f34e1c61dbf6a6cef173e434af595857fd0","datavalue":{"value":{"entity-type":"item","numeric-id":3802644,"id":"Q3802644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3451b0cedaf271c7d472b237417a8aa67802c346","datavalue":{"value":{"amount":"+0.93876433","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":"Q1186079$AF1F66FD-8381-4AFA-AA1E-1A695CE2EEA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9a6c388b03fe5f54ff6c843b692cff7c7ff6221","datavalue":{"value":{"entity-type":"item","numeric-id":5225521,"id":"Q5225521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb1b38e11ff89a08c38734724c118a6c8449cb52","datavalue":{"value":{"amount":"+0.88571465","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":"Q1186079$52563402-9665-49A0-B0E5-10B2D2065A42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33a236dfaf6e06b46fa3f1b7a61fc9ad4eea9387","datavalue":{"value":{"entity-type":"item","numeric-id":4362733,"id":"Q4362733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d8468ccc902bd142308ce1f9dc78f7d7fd8bf01","datavalue":{"value":{"amount":"+0.88398343","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":"Q1186079$F0B81498-4486-459A-982C-0B88E4758597","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f125994614c46898c419bfaf99aea17c20509de1","datavalue":{"value":{"entity-type":"item","numeric-id":3772259,"id":"Q3772259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f50d49cf21dd4d3a15aa9f94cb9d76d423507508","datavalue":{"value":{"amount":"+0.8815406","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":"Q1186079$6001013B-B5F1-4075-8C26-D128FE52EDAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33ce9d6c638e95d77fa3cc83f6b51b227ee42cc4","datavalue":{"value":{"entity-type":"item","numeric-id":2433714,"id":"Q2433714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1b61b03550159a44c1f796936d4e97b2d3a2950","datavalue":{"value":{"amount":"+0.8801238","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":"Q1186079$87E87A46-E0E4-4046-A314-90D7E3F32B5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e3a77e5800038cf5efe01fbb1a008683d5d2162","datavalue":{"value":{"entity-type":"item","numeric-id":1110525,"id":"Q1110525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27b5c4ccb50b686a9c67232461431208d5ba24df","datavalue":{"value":{"amount":"+0.87560785","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":"Q1186079$DE959749-07A6-44BA-ABF1-160F31CD5423","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"260d03ebabc69ed400497e8a28209ff3a063ba7d","datavalue":{"value":{"entity-type":"item","numeric-id":1092933,"id":"Q1092933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3347e5a3dabecd744d9ae198affadd6c88350c8f","datavalue":{"value":{"amount":"+0.8737253","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":"Q1186079$A3696A46-3351-4AD7-82ED-0ECB8F53390D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e30845bcc3c0e404f2f7000df25b44eac1a0ccde","datavalue":{"value":{"entity-type":"item","numeric-id":5053724,"id":"Q5053724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae5fa76af64a9537af7c9438f5cca20c8c1a7cb3","datavalue":{"value":{"amount":"+0.87295187","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":"Q1186079$FEA95BEC-9E9A-4036-8251-41905F0C9191","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65dc58360897ef600be3a74b9c2c5cca41824e4a","datavalue":{"value":{"entity-type":"item","numeric-id":4209944,"id":"Q4209944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"309ec22d17429e3425bd63b357397c5313bacb27","datavalue":{"value":{"amount":"+0.87262523","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":"Q1186079$C09B7A90-1E02-47BA-84F2-43E6734A01B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38ba67de00ccf2864f98e52bb6aba5b0fa894ce9","datavalue":{"value":{"entity-type":"item","numeric-id":4310718,"id":"Q4310718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"deda25e46cc3e4279176f7f9ca63898d003ec718","datavalue":{"value":{"amount":"+0.8683314","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":"Q1186079$EA57E07E-6540-46D1-984F-70C3917A0785","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Classes of graphs which approximate the complete Euclidean graph","badges":[]}}}}}