{"entities":{"Q1179762":{"pageid":1190511,"ns":120,"title":"Item:Q1179762","lastrevid":69837705,"modified":"2026-04-13T10:40:58Z","type":"item","id":"Q1179762","labels":{"en":{"language":"en","value":"On graphs preserving rectilinear shortest paths in the presence of obstacles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 25312"}},"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":"Q1179762$C585ECFE-F697-4ACD-AACA-5109DB9423B1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"08429b645d6bcc9299628d53e4a8c67142c20b54","datavalue":{"value":{"text":"On graphs preserving rectilinear shortest paths in the presence of obstacles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1179762$43610419-A0F1-4E51-916B-8AB2EFF2FE29","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d9db0409295a879a211faf54d746e4646cf6c151","datavalue":{"value":"0747.90105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179762$301D82AF-7010-414F-B0E5-655699BDEDE9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"594f5df991c275ed5c070e61bddd3826a6c58837","datavalue":{"value":"10.1007/BF02067242","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179762$E6905083-185E-41B3-AAC9-BEC71AB381B3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0327d5313d734dde2c609f96abfb0c99d20abfac","datavalue":{"value":{"entity-type":"item","numeric-id":539451,"id":"Q539451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179762$AB96D2BD-2B25-40F8-8C10-9A1C4ABCAD3C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8f57d1123ebbbd10d621b3552a672e7729202712","datavalue":{"value":{"entity-type":"item","numeric-id":59875,"id":"Q59875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179762$03BBAACE-0884-4ABE-92C5-C2B122907103","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70844ffc4666eabac4e20376c648613dbe8620f7","datavalue":{"value":{"time":"+1992-06-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1179762$231A4055-5CE2-4F1A-8FDB-AC24DDD119F9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b1d01f3a3586791018b84bd7091341b5a5932cea","datavalue":{"value":"For solving global wiring problems in physical VLSI circuit design, two stages are usually considered. The first stage is to compute from the layout geometry a graph that preserves all shortest paths between pairs of relevant points. The second stage is to operate on that graph for computing shortest paths, Steiner minimal tree approximations or the like. For a set of points and a set of simple orthogonal polygons as obstacles in the plane, with \\(n\\) input points (polygon corners or others) the author shows how a shortest paths preserving graph of size \\(O(n \\log n)\\) can be computed in time \\(O(n \\log n)\\) in the worst case, with space \\(O(n)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179762$E1109473-2DE8-4324-A459-6D3ECA977A9D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f4aed06ce87e48c8c58fd5d268ea91779fe40edf","datavalue":{"value":{"entity-type":"item","numeric-id":176697,"id":"Q176697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179762$EFE05C3D-770C-4A61-91A2-3552A55E15FC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179762$F9CF1633-25D5-492D-A132-BFDC1C8CB73A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179762$71FA7677-EE85-4DBA-955F-1130E92C582B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179762$ED355018-E94E-49AB-AEA9-2DB8EC9B8BD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3cb322112ae56aec500b334b7351f32fb107365","datavalue":{"value":"68W35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179762$0A9600DC-1A01-4F2C-88D9-81D1990017AD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0f9fd2a1030212a83b64276cc058872fad45ec64","datavalue":{"value":"25312","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179762$2F297A01-5CB3-462B-81D7-A452DD071ABC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62178c3024e86d9b40bbec46dd2d464583365ad7","datavalue":{"value":"VLSI circuit design","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179762$0AD0E0E1-FCBB-4F6B-8186-F16A6CE03E4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69d0c99f1e5283b31715a9c7d799852fe62c506e","datavalue":{"value":"shortest paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179762$12122333-8816-4C13-AEC2-BBC34D76728E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd37eb4ab6de574ff69b6f295805ede0ca5c432d","datavalue":{"value":"Steiner minimal tree approximations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179762$EF1A3E7D-0EC0-47B0-B0EC-07CEADA7032B","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":"Q1179762$04C7EFD2-6481-45D4-A691-9422339D2214","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"af897edd69650b0fb523f1e28b3483b5592bf862","datavalue":{"value":{"entity-type":"item","numeric-id":3474275,"id":"Q3474275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179762$9CCF3607-1DFD-4B08-9832-00A4061C325C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa1ba3f58e2231825bfce74b74cabb3c6d2ddd9e","datavalue":{"value":{"entity-type":"item","numeric-id":1087340,"id":"Q1087340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179762$7CA836B8-236B-4D5A-A85F-A314F0D14885","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e5e15be2fc2d7b9cbc214ed3a39df3b7a8c79df","datavalue":{"value":{"entity-type":"item","numeric-id":1109046,"id":"Q1109046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179762$D5444E00-9F3E-45A2-851B-9EEC5F69A490","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed0977a4d9c5a2ae05d317388867f5553ed3a501","datavalue":{"value":{"entity-type":"item","numeric-id":1079135,"id":"Q1079135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179762$8368FD3E-B6B8-4115-81B2-E92367236A73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a47d1241b02e1d0bbfbf624b5f79557aca4ffd76","datavalue":{"value":{"entity-type":"item","numeric-id":4182533,"id":"Q4182533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179762$D0F4C636-9545-49E7-A9A1-71F9DB3A7496","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fa100a17563267c9ce7aba954cad30e5fab5c56","datavalue":{"value":{"entity-type":"item","numeric-id":4143183,"id":"Q4143183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179762$2B0A3AED-6340-4405-BC4E-8496104E0EEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b57ae0178b078a7805d69f23f6f3821c98a2cd7","datavalue":{"value":{"entity-type":"item","numeric-id":3673101,"id":"Q3673101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179762$828A271D-32EE-4AAD-A99C-1FB39FE0CECC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08bbfa2750c080ec67d6b7bc35b58e0a9bc36c96","datavalue":{"value":{"entity-type":"item","numeric-id":3694703,"id":"Q3694703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179762$D6A2AA26-EB75-4ED0-93F6-B775AF482C26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ba287703bcdfe2f73ef8b56b1010aaf445322c3","datavalue":{"value":{"entity-type":"item","numeric-id":4694752,"id":"Q4694752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179762$F3815327-738A-4F4E-9E6D-18954104BB34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28d1d1cb66d27d2e53aba37392ad47b61e11f859","datavalue":{"value":{"entity-type":"item","numeric-id":3326832,"id":"Q3326832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179762$EB55B0D8-07E6-4305-A5C0-DF129F6DBCF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ffec4d94b7b012095f39126ed96f3bf822347da","datavalue":{"value":{"entity-type":"item","numeric-id":1062764,"id":"Q1062764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179762$E7BDCD8F-7D1C-4DC1-B5ED-A429D90459A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83cafa61616459ab17ac21c79c7cb73811e69410","datavalue":{"value":{"entity-type":"item","numeric-id":3028355,"id":"Q3028355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179762$18A9B7BE-2C3B-4474-A427-E30349A80537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7761f5a7d78fdf6a95c7409831365b923fe504b6","datavalue":{"value":{"entity-type":"item","numeric-id":3790913,"id":"Q3790913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179762$02969BB9-9449-4DD6-8840-566133AF9191","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb47a342e9089be25243758908fc7ce1d12f73c","datavalue":{"value":{"entity-type":"item","numeric-id":3783226,"id":"Q3783226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179762$3954DFEC-789A-40FB-89C2-979934E10FEC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"acb129ea5be3104387090368db06248f41f6c116","datavalue":{"value":{"entity-type":"item","numeric-id":4483819,"id":"Q4483819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3096af05bf390412df12e7d69f106f968b5ca339","datavalue":{"value":{"amount":"+0.7896281480789185","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":"Q1179762$B9ED7542-95D3-47E1-B2B9-174A239B7708","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd0d87b49de1824c2b0d37e0f0d6b5bc3bdee90d","datavalue":{"value":{"entity-type":"item","numeric-id":5943315,"id":"Q5943315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87a4a2edc231d5db1afed9d67808ca2ef7b2a828","datavalue":{"value":{"amount":"+0.784887969493866","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":"Q1179762$63EF85FA-9241-40BB-A099-EC2A7A6D4291","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"755af88bd04bcf8c26ace493cef6bd5cb6f61f98","datavalue":{"value":{"entity-type":"item","numeric-id":3337244,"id":"Q3337244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42ab38b86b5350aaab2653661437b52c3d04f123","datavalue":{"value":{"amount":"+0.7785119414329529","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":"Q1179762$A127DEA6-B200-4F12-95A7-153D661CD648","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a89aa1bd206c38ae6d7f4e0bf61af0ec38a5200","datavalue":{"value":{"entity-type":"item","numeric-id":2563920,"id":"Q2563920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66441173a6cd4a83a8f11e95d0c65e9f0ff67c88","datavalue":{"value":{"amount":"+0.7770246863365173","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":"Q1179762$C9B542F1-F136-415A-BDFF-E5589B4E389A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On graphs preserving rectilinear shortest paths in the presence of obstacles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_graphs_preserving_rectilinear_shortest_paths_in_the_presence_of_obstacles"}}}}}