{"entities":{"Q1283768":{"pageid":1294518,"ns":120,"title":"Item:Q1283768","lastrevid":70575444,"modified":"2026-04-13T15:33:13Z","type":"item","id":"Q1283768","labels":{"en":{"language":"en","value":"Approximate shortest paths and geodesic diameter on a convex polytope in three dimensions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1271046"}},"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":"Q1283768$8CE5A495-97D3-434C-B14B-718A7C915CAB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dcd9895dbde20c11b719c8f13671fec374a9f549","datavalue":{"value":{"text":"Approximate shortest paths and geodesic diameter on a convex polytope in three dimensions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1283768$D3765FBB-DA29-409F-A7ED-6ED7A85E358E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3ad2cae58195230384a7ea1a529b42334cf8eb83","datavalue":{"value":"0922.68119","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283768$0A4EAEE6-9394-457A-A1A6-18D64CB53EC5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a9528d51f7335a12f092e6c2d2d97373437610ce","datavalue":{"value":"10.1007/PL00009417","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283768$824E5E45-5275-4767-91E0-6455B22ABFB1","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":"Q1283768$922E8F81-0163-41B2-BE2A-45E312AEBE00","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5cd551a6d332eac1488fffbdc2716ff15f0d6f26","datavalue":{"value":{"time":"+1999-09-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1283768$B03D55A5-879B-46FF-BEB7-60A0A692C7A1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4490f9d7a5fcb519b3923e9c132331584a38c81f","datavalue":{"value":"Given a convex polytope \\(P\\) with \\(n\\) edges in Euclidean 3-space, the author presents a relatively simple algorithm that preprocesses \\(P\\) in \\(O(n)\\) time, such that, given any two points \\(s,t\\in\\partial P\\) and a parameter \\(0<\\varepsilon\\leq 1\\), it computes, in \\(O((\\log n)/\\varepsilon^{1.5}+1/\\varepsilon^3)\\) time, a distance \\(\\Delta_P(s,t)\\) such that \\(d_P(s,t)\\leq\\Delta_P(s,t)\\leq (1+\\varepsilon)d_P(s,t)\\), where \\(d_P(s,t)\\) is the length of the shortest path between \\(s\\) and \\(t\\) on \\(\\partial P\\). The algorithm also produces a polygonal path with \\(O(1/\\varepsilon^{1.5})\\) segments that avoids the interior of \\(P\\) and has length \\(\\Delta_P(s,t)\\). In contrast, the fastest known algorithm for computing a data-structure that supports queries of computing the length of the exact shortest path between any pair of points on \\(\\partial P\\) is due to \\textit{P. K. Agarwal, B. Aronov, J. O'Rourke} and \\textit{C. Schevon} [SIAM J. Comput. 26, No. 6, 1689-1713 (1997; Zbl 0891.68117)]. It requires \\(O(n^6m^{1+\\delta})\\) space and preprocessing time, for any \\(\\delta >0\\) and answers a query in \\(O((\\sqrt{n}/m^{1/4})\\log m)\\) time, where \\(1\\leq m\\leq n^2\\) (the constants of proportionality depend on \\(\\delta\\)).    The author also presents an algorithm that computes, for a given convex polypote \\(P\\) with \\(n\\) edges in Euclidean 3-space and a parameter \\(0<\\varepsilon\\leq 1\\), two points \\(s, t\\in \\partial P\\) such that the geodesic distance between \\(s\\) and \\(t\\) is greater or equal than the geodesic diameter of \\(P\\) multiplied by \\(1-\\varepsilon\\). The running time of the algorithm is \\(O(n+1/\\varepsilon^5)\\). In the contrast, the fastest known algorithm for the exact geodesic diameter takes \\(O(n^8\\log n)\\) time (see the above mentioned paper by \\textit{P. K. Agarwal} et al. for more details).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283768$A631B5F7-D1B5-4DEF-BC66-50E38859909C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"701be6ec4b25c9dfd38ab9bbe2b2271154404d34","datavalue":{"value":{"entity-type":"item","numeric-id":205832,"id":"Q205832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283768$3EC0D8E4-0D3B-44E2-8405-C3FDC9CAFB6E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283768$4C413ED2-1671-4F4C-B132-703119B66023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"78931806833c54190437f3675cf624ba3d256107","datavalue":{"value":"52B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283768$E40F6764-1E33-4138-82BE-1A689C8DE0B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"25e0d182f9209de8bdd0e1e38d29199d5601bf84","datavalue":{"value":"52B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283768$2F0BF2F4-8F8B-4470-B741-E58E9BA9F111","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283768$40F9E927-ED2C-48C1-ABDA-A57D83F02017","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"14b84f79de2781394700de9405bba9e5661b93fb","datavalue":{"value":"1271046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283768$F4001B68-BF9C-49E4-83FC-C81DBD2C9826","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7182560e36f1aae71088c0032075b2b85ff39acd","datavalue":{"value":"three-dimensional Euclidean shortest-path problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283768$F820A59D-4CE1-4A07-B1FB-12BD640E54E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad2b60cc4290a2f805ccaf91f481c908f8b73b04","datavalue":{"value":"approximate three-dimensional Euclidean shortest-path problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283768$6E5D4B08-E920-4725-B788-2B44A95CDF74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d2581dfc73dad211d8c23eb5bd612089990af7f6","datavalue":{"value":"approximate shortest-path queries on a convex polytope","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283768$BAD927E1-840C-431E-853A-DEA0AFF473F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a406cdd8bc89fc9ffbc707b36ceb7fb1604a2ba9","datavalue":{"value":"approximating the geodesic diameter of a convex polytope","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283768$6ECD4BA5-7FC3-47DF-8845-2D1AB44047E1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"06885e4ccb9c846e3cd419bb7d9235a62bcac08f","datavalue":{"value":{"entity-type":"item","numeric-id":247175,"id":"Q247175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283768$C74653AB-8560-46D4-93C8-6C771083B2A3","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":"Q1283768$3C556F21-0C28-4646-ADDA-E2C73EACF651","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"12bfc9f4b126e91308702f6b237e1aa840d96ca4","datavalue":{"value":"https://doi.org/10.1007/pl00009417","type":"string"},"datatype":"url"},"type":"statement","id":"Q1283768$812017EB-2A5C-487F-81E3-4F4165D39BC4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6d3a6e95b7d908995c90024a2e44af576c51946a","datavalue":{"value":"W2063071084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283768$9AEAE733-D774-4030-B433-7CE5DEDFB10D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c953bac7f737210537c6c2823afafdfb7b012748","datavalue":{"value":{"entity-type":"item","numeric-id":4377587,"id":"Q4377587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2b03f3d8c2f9787ba206f35e1b52dde432a6413","datavalue":{"value":{"amount":"+0.923653244972229","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":"Q1283768$A7252F2E-4CDC-42F5-A207-A5A259FDE620","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ce8491164c38e39b133bc5a169443afb88dbb7d","datavalue":{"value":{"entity-type":"item","numeric-id":4886077,"id":"Q4886077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4743d3e796030b70b09ac649e66dc5f3ef5552c","datavalue":{"value":{"amount":"+0.9053166508674622","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":"Q1283768$6F13EC85-A26A-4A79-AAC8-018807D90891","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1dbe511f7027a99c6a3089ff8362ae68a5c8528","datavalue":{"value":{"entity-type":"item","numeric-id":1388131,"id":"Q1388131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68f3240ab51a40d0e6c62ef55ee9bf90ebae746b","datavalue":{"value":{"amount":"+0.9000339508056641","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":"Q1283768$34DA0761-A26A-475B-96BA-0B4140FD788A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"895b86dd49b9ec62cc058413ae07d3ac9ad6242c","datavalue":{"value":{"entity-type":"item","numeric-id":1601017,"id":"Q1601017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8cd96a62772c1524c8c271b78f61a6cf0499581","datavalue":{"value":{"amount":"+0.8751183152198792","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":"Q1283768$A0A70E38-997B-4AA3-96D0-85F3021E8014","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximate shortest paths and geodesic diameter on a convex polytope in three dimensions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Approximate_shortest_paths_and_geodesic_diameter_on_a_convex_polytope_in_three_dimensions"}}}}}