{"entities":{"Q1886240":{"pageid":1896982,"ns":120,"title":"Item:Q1886240","lastrevid":71673189,"modified":"2026-04-13T23:48:04Z","type":"item","id":"Q1886240","labels":{"en":{"language":"en","value":"Rotationally optimal spanning and Steiner trees in uniform orientation metrics"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2116167"}},"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":"Q1886240$5C69E73B-078B-4A33-85B9-B9323DC7E943","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"85ee88b484d64483491051c803e5172a1500460f","datavalue":{"value":{"text":"Rotationally optimal spanning and Steiner trees in uniform orientation metrics","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1886240$F85F4484-B4B4-4233-B4D2-2C34C2DDC711","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ba098fc4a534527a0ede504b267317807baa122b","datavalue":{"value":"1051.05029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1886240$31F71F52-70CF-4106-A981-ECD952BC4408","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"add7d5c33e1aab55e2a802df98fe168758c27ca9","datavalue":{"value":{"entity-type":"item","numeric-id":402216,"id":"Q402216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1886240$C46CE90B-2207-4CC5-8603-F4DA46F5B77F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d30a450a0e27ddd2629f61bec3b6801a9fd2f416","datavalue":{"value":{"entity-type":"item","numeric-id":1005324,"id":"Q1005324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1886240$A1A01E15-9734-406D-8FB5-A300C080E5E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"489811fbf8c6d8c0740c5fbd21d01b77d56cfbb9","datavalue":{"value":{"entity-type":"item","numeric-id":583879,"id":"Q583879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1886240$758FE7C2-BA5B-482A-BE5D-386669B5068D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b96ddf035774de40b2c1963e05a44e5c8c58c26f","datavalue":{"value":{"entity-type":"item","numeric-id":1402522,"id":"Q1402522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1886240$33A4E0D4-CC23-4400-BA9A-FA4D29CF8D69","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":"Q1886240$5A5653F6-C46B-4C6B-84AC-33A7EBF68936","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"037fcf95f864ae0e38f5b6894c4f594ea5ca568c","datavalue":{"value":{"time":"+2004-11-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":"Q1886240$975B00CA-3711-4251-A97F-F79E673ACDD3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4a1a6af952ca7ab2096a48fc813c81b64784f221","datavalue":{"value":"The following problem is studied: Find a minimum spanning and Steiner tree for a set of \\(n\\) points in the plane where the orientations of edge segments are restricted to \\(k\\) uniformly distributed orientations (\\(k = 2, 3, 4,\\dots\\)) and where the coordinate system can be rotated around the origin by an arbitrary angle. In the case where \\(k = 2\\), called rectilinear, the edge segments have to be parallel to one of the coordinate axes, while in the case \\(k = 4\\), called octilinear, the edge segments have to be parallel to one of the coordinate axes or to one of the diagonals.  As the coordinate system is rotated, while the points remain stationary, the length and topology of the minimum spanning or Steiner tree changes. A straightforward polynomial-time algorithm is proposed to solve the rotational minimum spanning tree problem. A simple algorithm to solve the rectilinear Steiner tree problem in the rotational setting is also given, as well as a finite time algorithm for the general Steiner tree problem with \\(k\\) uniform orientations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1886240$34C1E903-1F36-4526-97E0-0FB84660BB2C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1886240$5807B583-0FCA-4ABD-835F-CD27CE5DFAA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1886240$6CF8FC02-5B87-4D8B-944E-470E1B8275BD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"07754616eedd89b95109a51654d3929e1f7932ff","datavalue":{"value":"2116167","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1886240$9C5EEFD3-978A-4B4B-A4E9-8DACDA9C3C0D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66a0382610d9d9e28ef95c946357abf690b72349","datavalue":{"value":"Steiner tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1886240$9759587B-E645-4223-B7AC-024DF8DE8334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"862bb4054e9afacad3472d8b88ea0594e4c44b7b","datavalue":{"value":"uniform orientation metrics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1886240$17742F61-44F5-4AFA-ACDF-8B5AEBB55D30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcc34fede3fe13b5779f52f3b39c3bd302ecd414","datavalue":{"value":"rotational problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1886240$34261EE5-9124-4404-AC61-645DB4A27DC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38dd5c31d373d76e6308be0f17a0875fd182b166","datavalue":{"value":"VLSI design","type":"string"},"datatype":"string"},"type":"statement","id":"Q1886240$60A907EF-0D97-4768-BDAB-EA87BAB834AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1886240$F5788164-3E0F-4B09-9777-E15ECDABC620","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c82436212510eb3fd57a05c9debac7e41dff5f00","datavalue":{"value":{"entity-type":"item","numeric-id":226578,"id":"Q226578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1886240$3A10ED6F-65AE-443C-AEC1-6DF882BB922C","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"c892a7dec489f094d5c37de3901314ce53d5bea2","datavalue":{"value":{"entity-type":"item","numeric-id":16499,"id":"Q16499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1886240$725D73FE-AD40-4155-B917-D63059D2FAD8","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":"Q1886240$B6AA1402-8FAB-4134-B407-377873E073A5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bee9a4080d5ff769085c75217ad37b73dccc7621","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2004.04.001","type":"string"},"datatype":"url"},"type":"statement","id":"Q1886240$608B7264-DCA6-478D-9191-3BE150CABE29","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9532dc23729cda1964e23fa3a5b901e014344a7f","datavalue":{"value":"W2079608245","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1886240$3F797F66-240D-4A2B-95C3-A843A30CBFCD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"da7e31b1f61aeab13d730e35e07b09b03d4eb34c","datavalue":{"value":{"entity-type":"item","numeric-id":2706126,"id":"Q2706126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1886240$27E91003-29EF-4AE3-8D32-2812BDA944FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca56aa5e19160d277e580323bbda941316a8aa11","datavalue":{"value":{"entity-type":"item","numeric-id":2498405,"id":"Q2498405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1886240$497E644E-0459-43D2-BE2A-50A4E23EB5CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05676be0daa6c383cd4ac19d6e6ece33abc778d8","datavalue":{"value":{"entity-type":"item","numeric-id":1347366,"id":"Q1347366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1886240$2D087F6D-C15E-4262-AB46-F4FA96F6A57E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec77237bc017c121d18e07b3b1bc5c1578a7f1de","datavalue":{"value":{"entity-type":"item","numeric-id":1068839,"id":"Q1068839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1886240$43F05BF1-448A-4705-9B3A-00648C33EC25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ad8038f8a07799f6a016b4a2f17f5c375cbf128","datavalue":{"value":{"entity-type":"item","numeric-id":1202044,"id":"Q1202044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1886240$645EF7F2-B1FA-46C4-B97E-AD027CC51DF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f1212c060702ba52b9cf2a63b1deefd38e28190","datavalue":{"value":{"entity-type":"item","numeric-id":4411408,"id":"Q4411408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1886240$E5476578-F2ED-4306-B9A8-C7381E729774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62762281d99910d6089831154171dab10b7a9181","datavalue":{"value":{"entity-type":"item","numeric-id":1853076,"id":"Q1853076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1886240$7C308F50-7614-421A-ABFB-2C41F5C20A5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c72fe888066706c49fcc6b07b3331954b172008b","datavalue":{"value":{"entity-type":"item","numeric-id":4519132,"id":"Q4519132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1886240$78B1BEFD-1E7E-4C11-B336-596F53E5CBCB","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":"Q1886240$8654FEAA-B9C7-4EC8-BE71-FECACBC88966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97e622a45e3cbce577c4e3335928a443523652f3","datavalue":{"value":{"entity-type":"item","numeric-id":4363408,"id":"Q4363408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1886240$48CE19A2-4A5D-4731-8642-E2DE4F76AAF2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ffc3066e04ae6665968b3a8676c69e956ba5d7a0","datavalue":{"value":"10.1016/J.COMGEO.2004.04.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1886240$3CC75DB0-8B84-4578-9932-B36D41FF9E53","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc7a38db8aa0e31ccf8e75caf4ea29f0d1552f91","datavalue":{"value":{"entity-type":"item","numeric-id":2498405,"id":"Q2498405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"edf59a0476eea763c21d306fb72bdfefcddc0ff5","datavalue":{"value":{"amount":"+0.8519030213356018","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":"Q1886240$B1A73AEB-1880-4CAC-BB15-41A747A066A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1204c71f87172713d26c72ebef222bd4b145ba5","datavalue":{"value":{"entity-type":"item","numeric-id":3595417,"id":"Q3595417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c8e8d7697773443a2c9fdb33082b5e7c0e764d1","datavalue":{"value":{"amount":"+0.8367359042167664","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":"Q1886240$A5C0343C-4306-429A-9F83-3CDE2E48F80E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bee8763e1b0a495df26cf1af0086d95ed7e76d3","datavalue":{"value":{"entity-type":"item","numeric-id":1029671,"id":"Q1029671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4934c01fa7ca2f683a8f93ba7ddffec9ea7928b","datavalue":{"value":{"amount":"+0.8329798579216003","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":"Q1886240$FCFBD6AC-FECB-4C5A-ABC0-3CCAD602F34F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d27611d8ea31f2529cd620efd2662875cc341968","datavalue":{"value":{"entity-type":"item","numeric-id":1384537,"id":"Q1384537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25faf056822c2bc1ae237039588f13884506b543","datavalue":{"value":{"amount":"+0.824060320854187","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":"Q1886240$D4E1F4F1-F2CD-4EBA-9DCC-6B50326859A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d71ba8b0971b3a532b8545b8415d722af04ca00","datavalue":{"value":{"entity-type":"item","numeric-id":4506270,"id":"Q4506270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76db8cc65adc7bf9ace5c364af2e746c5444bff6","datavalue":{"value":{"amount":"+0.8123032450675964","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":"Q1886240$224DA257-7D96-4BBC-91D0-439A11EDB264","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Rotationally optimal spanning and Steiner trees in uniform orientation metrics","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Rotationally_optimal_spanning_and_Steiner_trees_in_uniform_orientation_metrics"}}}}}