{"entities":{"Q419498":{"pageid":421265,"ns":120,"title":"Item:Q419498","lastrevid":51470432,"modified":"2026-01-18T09:58:11Z","type":"item","id":"Q419498","labels":{"en":{"language":"en","value":"Querying two boundary points for shortest paths in a polygonal domain"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6036554"}},"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":"Q419498$B523B627-F032-4B5E-9665-979EFF56E4F5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1fe7c705e2cca0a638fa31cc0ecb2c5c5359f353","datavalue":{"value":{"text":"Querying two boundary points for shortest paths in a polygonal domain","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q419498$A0F2AA6F-AE0C-4A26-8E66-04948A5B031C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0e10926d45838e251bdd4c540f17371bd646218d","datavalue":{"value":"1266.65033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q419498$EEE67192-07F3-4917-B779-5F69FA2E9700","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aad2244a0fac49ecd6eb575ec97eea59fe9c09ce","datavalue":{"value":{"entity-type":"item","numeric-id":283874,"id":"Q283874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$B08AE83D-E050-464C-9DEA-F38C2AEFB27D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"588f81d5d873db739b77dc3bd5e8c0569a577232","datavalue":{"value":{"entity-type":"item","numeric-id":304266,"id":"Q304266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$5E6C7F20-BA2F-4668-96F1-6583B97C529A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$86C4091C-1520-42EF-9D9B-5EAF8495DD22","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cce433cdcb3478d8106ca3fd120344ac0deb7f83","datavalue":{"value":{"time":"+2012-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q419498$D8856112-B40F-4F8B-AF3E-5C6B40ACDC4B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c9684a93e5f98988685744c9cbf253435c411cf8","datavalue":{"value":{"entity-type":"item","numeric-id":510384,"id":"Q510384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$80D14BF9-FD7A-4F7F-90CE-6F1F44C87280","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q419498$409078F1-3ED5-44B6-8AC8-71FEF415B2AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q419498$11CAFA11-B6CA-4B27-9250-E086A3FEDA38","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"785e51c0499b4181e6bc12b8c0847103f37e88d5","datavalue":{"value":"6036554","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q419498$755FCC4B-0DE1-49D1-8CFA-D52506487062","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36a51744b74cc671801acb5ba4bcdd21474af9d6","datavalue":{"value":"shortest path query","type":"string"},"datatype":"string"},"type":"statement","id":"Q419498$37040E3A-531A-4365-8596-5A363B084D0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e4294b29473d50b572233d4cdc3339d3770d262","datavalue":{"value":"polygonal domain","type":"string"},"datatype":"string"},"type":"statement","id":"Q419498$BD71A038-534D-4577-AA4E-3E6E21C90E59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8ecb9ba39ffdb1ea2c5ee33c86530ae7c9cba72","datavalue":{"value":"Davenport-Schinzel sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q419498$0E630597-9DBD-481D-A77A-0B343AB2C776","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":"Q419498$6BD042BC-7269-475B-B90E-0830D2F6C259","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2bf84fb526a9b6c6e4f5370142d134e8407d99eb","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2012.01.012","type":"string"},"datatype":"url"},"type":"statement","id":"Q419498$807F61C3-2165-4161-BD3C-9EDD8BBD73FA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b3c1e165ef89d9e8b29e55ed9d8aaeb4f3297de7","datavalue":{"value":"W2138769733","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q419498$7BC3BE9E-2564-4E59-BFEA-E690DC84D89F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"73dca722580e72e13fc7309b89e096640257fccf","datavalue":{"value":{"entity-type":"item","numeric-id":4376190,"id":"Q4376190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$58AA125F-16BF-41A1-AD1C-39C172F54807","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bddf2d80afe8337190cc58b16d74c8622b209ca3","datavalue":{"value":{"entity-type":"item","numeric-id":4376194,"id":"Q4376194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$25EA5D98-1D2D-499A-8431-33BD375D5270","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"782dc3c835abd1a10457fabfd0d5cfc6d59ecaf4","datavalue":{"value":{"entity-type":"item","numeric-id":4945502,"id":"Q4945502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$0086D78F-E90E-476A-82DC-6339D25E9ABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f29d5232ef41f1d74ad6f96b4d89caf068895dda","datavalue":{"value":{"entity-type":"item","numeric-id":4595512,"id":"Q4595512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$B729BB5E-C727-4668-909C-D6E94724559E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e46012c1e8022041de5d6843e63b4d32e6d7dae6","datavalue":{"value":{"entity-type":"item","numeric-id":4886059,"id":"Q4886059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$E0D8C9B2-A8D3-4589-872A-6DC17E6D4119","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"394dd0a1db136114267061e6879ec698b3dcf8fa","datavalue":{"value":{"entity-type":"item","numeric-id":4252291,"id":"Q4252291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$C2A59587-78F8-4D35-BFC0-F096667F3292","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10f46265f70e1208a0c7557b0cc79b607bfa9aea","datavalue":{"value":{"entity-type":"item","numeric-id":3183449,"id":"Q3183449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$615B5314-9E60-4F26-9EA8-FC128C0F2E88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78ad3e344884042a22c9826d03bd0164d31b90d7","datavalue":{"value":{"entity-type":"item","numeric-id":1823689,"id":"Q1823689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$A9DFFC21-F763-4056-BD34-175E2FCF5E0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae68a3ad7b25f6e33d7bf48ec3a6985113443b72","datavalue":{"value":{"entity-type":"item","numeric-id":3511429,"id":"Q3511429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$89DF66F5-C94C-43F6-9FB0-54BE31CA6764","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83f629c180f6436ab6ea9a75b06b545548804bab","datavalue":{"value":{"entity-type":"item","numeric-id":4143433,"id":"Q4143433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$1D83DAAC-D956-4E59-A3D6-09F862374226","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cb785b1fa00468f72c20fed51d4e390b8834f38","datavalue":{"value":{"entity-type":"item","numeric-id":582095,"id":"Q582095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$4F676913-B8D9-4AE6-A211-5A697066779A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bd53defd1b885afb6fd232d4d93b234faab9514","datavalue":{"value":{"entity-type":"item","numeric-id":4268866,"id":"Q4268866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$909EC64B-D0BC-489F-A38B-27BBB35E129B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf272138c0f0cb723f48929502d668d4ad806845","datavalue":{"value":{"entity-type":"item","numeric-id":5687652,"id":"Q5687652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$2AE88508-14A5-407A-8E0E-4FAD090B13F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"743c8062e07d18cd64ec304f9ff8ddbc241d0b7d","datavalue":{"value":{"entity-type":"item","numeric-id":3578194,"id":"Q3578194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$1FC5E648-15DC-43C6-9A48-936B84FB1E5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4dfbe8e6db8b926493b239e8b1a357e8fc5bf74a","datavalue":{"value":{"entity-type":"item","numeric-id":1338960,"id":"Q1338960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$9278F4AA-A296-4DEA-AE15-2CFB881F2CEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf78f24dc9967d0a6148cbfe129076e5e338f2c7","datavalue":{"value":{"entity-type":"item","numeric-id":4325546,"id":"Q4325546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q419498$2E8B466B-8753-40E8-A429-28E9964EB16B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"160e10462672950b7dab995283f312aef225e0cb","datavalue":{"value":"10.1016/J.COMGEO.2012.01.012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q419498$599F7AC9-555F-44A1-9D10-3E4F005AEE71","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4d1df92870a981893fca8b084702b225010e8ba9","datavalue":{"value":"Let \\({\\mathcal P}\\) be a polygonal domain (with holes) in the plane with \\(n\\) corners. The authors present a data structure that allows for the determination of the shortest path between two points on the boundary \\(\\partial{\\mathcal P}\\) in \\(O(\\log{n})\\) time. The shortest path \\(\\gamma_{u,v}\\) between two corners \\(u,v\\) is necessarily a sequence of line segments adjoining pairs of other corner points, whereas the shortest path between two boundary points \\(p,q\\) is either the line segment \\(\\overline{pq}\\) or the polygonal path formed from \\(\\overline{pu}\\), \\(\\overline{vq}\\), and \\(\\gamma_{u,v}\\) for some \\(u,v\\). Using a parametrization \\(\\alpha\\) of \\(\\partial{\\mathcal P}\\), the authors write the length of such a path between two boundary points as an algebraic surface \\(f_{u,v}(s,t)\\), where \\(p=\\alpha(s)\\) and \\(q=\\alpha(t)\\).NEWLINENEWLINEA data structure used to query the shortest path between two boundary points is then obtained from the minimization diagram \\({\\mathcal M}\\) that computes the lower envelope of the collection of all surfaces \\(f_{u,v}\\) with \\(u,v\\) corners of \\({\\mathcal P}\\). It is shown that this structure may be precomputed in \\(O(n^{5+\\epsilon})\\) time, and using the same amount of space. The authors further refine this result by providing a method of computing \\({\\mathcal M}\\) in \\(O\\bigl(n^4\\lambda_{65}(n)\\log{n}\\bigr)\\) time and using \\(O\\bigl(n^4\\lambda_{66}(n)\\bigr)\\) space, where \\(\\lambda_m(n)\\) is the maximum length of a Davenport--Schinzel sequence of order \\(m\\) on \\(n\\) values.","type":"string"},"datatype":"string"},"type":"statement","id":"Q419498$8F3E6CA2-2A36-4D81-BA79-F48AEE73ACFF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f08ebe2329b05418d4be80c4ae18933334f0768","datavalue":{"value":{"entity-type":"item","numeric-id":3652291,"id":"Q3652291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58635cbe7bb3dc8ce7aa483e5163437b552f7d76","datavalue":{"value":{"amount":"+0.9962937235832214","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":"Q419498$DFA22BCB-934C-4766-8FCD-F612CC55AFE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66fb0284275a4227562c234b8ef3065e99b94374","datavalue":{"value":{"entity-type":"item","numeric-id":4252291,"id":"Q4252291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fd1f4883c2a927f03bf91298bd787c2ebab9381","datavalue":{"value":{"amount":"+0.8461339473724365","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":"Q419498$9CB1B7D9-DE9C-4507-8058-69375D62A020","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b938389ddb8afbef405bbfd7557f46245c31bb6","datavalue":{"value":{"entity-type":"item","numeric-id":3511429,"id":"Q3511429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de83390c7b078c1061773c1eea26a7b497925f7c","datavalue":{"value":{"amount":"+0.8359871506690979","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":"Q419498$2994DAD1-57E3-425C-B4E7-F13A4ECBA8BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0a1db8892f59fb297ce01494bf1f6096fe03400","datavalue":{"value":{"entity-type":"item","numeric-id":1823689,"id":"Q1823689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec957e89782d5fe3738f0a2d90d92f8bd182788c","datavalue":{"value":{"amount":"+0.8313888311386108","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":"Q419498$6DAA6405-0346-4C5B-AB16-BD23C88EA72A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d7a9aede34321fa76f7efa6fd242b6498bf19d8","datavalue":{"value":{"entity-type":"item","numeric-id":2316797,"id":"Q2316797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf952c2606b4dc9a6cf199e1e8cbf1290e55c8bd","datavalue":{"value":{"amount":"+0.8075447678565979","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":"Q419498$A75F9C53-E829-46B8-AD99-8C6BFD2E95F1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:419498","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:419498"}}}}}