{"entities":{"Q634249":{"pageid":636097,"ns":120,"title":"Item:Q634249","lastrevid":63137637,"modified":"2026-04-11T10:49:52Z","type":"item","id":"Q634249","labels":{"en":{"language":"en","value":"Reconstructing orthogonal polyhedra from putative vertex sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5935109"}},"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":"Q634249$CBB4404F-547E-4C75-914A-47BEFB273FB8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d2157ac3c48147e5dfe49c0fa86f2d26baf8cbb4","datavalue":{"value":{"text":"Reconstructing orthogonal polyhedra from putative vertex sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q634249$6A10CD37-814B-47A2-8894-E68CAA3BE9EB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0ddf53a99900b0f10856e88d08b82d3425df9a11","datavalue":{"value":"1225.65026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q634249$284A3724-D9A1-4C64-9E8F-11310F78E8BC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"53f7155c971c8e656de0929d61a01cfa7f4a8a96","datavalue":{"value":{"entity-type":"item","numeric-id":283885,"id":"Q283885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634249$E8921F49-4F7E-4C80-B020-49955966E20F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8be65cd66158c7fd5243610acab29184eef6acf8","datavalue":{"value":{"entity-type":"item","numeric-id":293200,"id":"Q293200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634249$E2DAAEF0-1373-44E3-B40B-168734D75CC1","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":"Q634249$E9CC6C55-6398-48EA-B9FB-1CDBA893A7DB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"eae8f23e25c6cbe921893b1ecf672f5812151386","datavalue":{"value":{"time":"+2011-08-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q634249$B69FC4C9-507E-4FFA-AA16-2FF06DD730AE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c07985759658986e41fe98901266d89f7699effc","datavalue":{"value":"Given a set \\(S\\) of \\(n\\) points in 3D space, the problem is to find an orthogonal convex polyhedron for which this is a set of vertices. If it is the intension to characterize the polyhedron only by (some of) its vertices, the uniqueness of the solution is relevant. An \\(O(n\\log n)\\) algorithm is proposed to find a unique solution to the problem (i.e., the orthogonally convex hull of \\(S\\)).  The problem becomes more complex if first a rotation \\(S'\\) of \\(S\\) has to be found before the polyhedron is constructed. This requires an \\(O(n^2\\log n)\\) algorithm. In this paper, first an \\(O(n\\log n)\\) algorithm is given to solve the problem in 2D (if the rotation exists, it is unique). Then this is used to solve the problem in 3D with a complexity \\(O(n^2\\log n)\\).  Some brief remarks, mostly open problems, are given for the case when additional points (on or inside the polyhedron) are prescribed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q634249$009EA484-A7AD-4384-A24E-DA64A08FD54A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q634249$8A9B58E0-1B70-4720-9D47-F7E51CE79570","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q634249$282E15A3-B326-4BB5-B08F-6FE09102794D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2762df744fec88c5da60f696833f02907bd4417a","datavalue":{"value":"52B55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q634249$FABD50F6-A6B4-451F-8E99-14C2020BE6ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a784276b4e09d379c8147965411b455c3d79751","datavalue":{"value":"68T10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q634249$54D1A561-B2DD-4BBE-9F81-E748F4707CEC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e3b8e2eb795bd20a395b52cd47c66f06c127c777","datavalue":{"value":"5935109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q634249$0CBC21C0-D7E2-47BC-95C8-84654B976179","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20cb5f900346d6218be2e7d1c87b3ca77a3b494d","datavalue":{"value":"reconstruction","type":"string"},"datatype":"string"},"type":"statement","id":"Q634249$A29CE82A-C999-4263-9A95-C1C7BF920E58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"049ed8a155990e3f7831e1a99b3182060bf447f3","datavalue":{"value":"vertex set","type":"string"},"datatype":"string"},"type":"statement","id":"Q634249$D7FF4845-19D4-4998-9660-9306F9B6A774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dfa11c9343eff8f5587f06426557a926ef37731","datavalue":{"value":"orthogonal polyhedra","type":"string"},"datatype":"string"},"type":"statement","id":"Q634249$6CFBBFED-0DC1-45D7-A4F9-92ACC8024FD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b508eb9c171301d8939bcc797b0cd89d2ccbd533","datavalue":{"value":"pattern recognition","type":"string"},"datatype":"string"},"type":"statement","id":"Q634249$EDEC56A2-1B16-441A-85CE-019B76820472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"069c4720b14dd0787953260e6765d397d85d5685","datavalue":{"value":"object recognition","type":"string"},"datatype":"string"},"type":"statement","id":"Q634249$B94D7B82-BF60-4781-ABD2-150EAD0E7CC2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"fc8a96e7da0a25d97c6c3415d8dffbc5c07a46e1","datavalue":{"value":{"entity-type":"item","numeric-id":283199,"id":"Q283199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634249$56148EE3-932A-4191-8B09-2FD07EDA75FE","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":"Q634249$99813817-EDCC-4EC4-9426-83D50225F2BD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f9ef32a38bb3033f7edb496bef4c26d060dfde68","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2011.04.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q634249$9FFE1433-4B04-428A-8AA2-43ED6ADD16B7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b84ad28ca820cfe2aee1a761fadce2c6782b3ff9","datavalue":{"value":"W2083269131","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q634249$AE2397D7-E5E0-4E29-A984-3B77137354CC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d9b35b254a8ef4c5a8b238e91c9f88994c67a51","datavalue":{"value":{"entity-type":"item","numeric-id":3796758,"id":"Q3796758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634249$D56F1803-8A3F-4135-8F74-B20D09F36BFA","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":"Q634249$7855D9B7-B3FE-4FA9-8BF3-BB4C62852942","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a740d882b0f53ab305b0df0cbe6f03c4603339e3","datavalue":{"value":{"entity-type":"item","numeric-id":4249563,"id":"Q4249563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634249$AC2B85DE-5B13-40FE-8F04-EEA9ADF7C342","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50bc3d2094879f8930d43fcea503e00f69a1e310","datavalue":{"value":{"entity-type":"item","numeric-id":2816149,"id":"Q2816149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634249$3B12761F-9D3C-47A3-8C07-BBB8B5DBB16F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6776598207b23f038c36462981533249230bc0f9","datavalue":{"value":{"entity-type":"item","numeric-id":2462350,"id":"Q2462350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634249$2AEE5326-7B01-43E4-8705-79EF0E542734","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97a507a1a9ee29fdd2a0fc77d58e8718deabc0e3","datavalue":{"value":{"entity-type":"item","numeric-id":4873187,"id":"Q4873187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634249$2C8BC6B5-A88E-43AB-9BA1-6E5046B20386","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64829d9ff241e50d45dd83ee65cd02f1800630b8","datavalue":{"value":{"entity-type":"item","numeric-id":802314,"id":"Q802314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634249$A7FAD864-E67D-4FC6-A273-AB283FA26823","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9db9a07d3fd244eb855961e15658777dfeead1cc","datavalue":{"value":{"entity-type":"item","numeric-id":3796310,"id":"Q3796310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634249$1D8334EE-A7FD-41FD-8C5D-74A57CBD44F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b3bf694a6a6f731a2788fe1e7847f97f71f5c73","datavalue":{"value":{"entity-type":"item","numeric-id":3611865,"id":"Q3611865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634249$E9B0D11C-212D-4500-8363-DE2327E9A157","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f5ad3ea62f9a812eeb7b78c3fc38b69a10024ccc","datavalue":{"value":"10.1016/J.COMGEO.2011.04.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q634249$1783FF94-F6C7-49FE-9156-AEF1486C94CF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86f0d013ab0d073240daab002b2ffc9b27448b56","datavalue":{"value":{"entity-type":"item","numeric-id":2999095,"id":"Q2999095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76f531d6798c9a793105eedbe527dfbd1e8fb5ec","datavalue":{"value":{"amount":"+0.7936813831329346","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":"Q634249$4ED80113-35A1-454F-9BC2-646E285DB68A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f82d2ee3fc8ad6c9e4d3868581d939a0fee8d950","datavalue":{"value":{"entity-type":"item","numeric-id":3652273,"id":"Q3652273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bd33d0d62f672624666556db273598afcd4e49c","datavalue":{"value":{"amount":"+0.7851916551589966","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":"Q634249$803753F5-5F17-4B41-AFE7-32B390FFC561","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2b54812858cd033d7d288b3bf0115e314f94738","datavalue":{"value":{"entity-type":"item","numeric-id":5458852,"id":"Q5458852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9d706a2f915f7b2291c949ab3f4e9e191e1b8e7","datavalue":{"value":{"amount":"+0.7848917841911316","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":"Q634249$1E1AD4AA-3B75-4520-ACA9-C102C61C96BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd46ae85bbaf0d06d60c939a9941dc934c293dc2","datavalue":{"value":{"entity-type":"item","numeric-id":3796758,"id":"Q3796758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2eba337df7238293cf7a825cae8f2db7ecfd9f1d","datavalue":{"value":{"amount":"+0.7613591551780701","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":"Q634249$7E4DF1F2-B832-4DFE-83E7-94F6DA1FAFE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92409a758b03459b1be0a364c162c8bf888b25cc","datavalue":{"value":{"entity-type":"item","numeric-id":4249563,"id":"Q4249563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f796612e76e18284393b0684a8b0a5bcc4fb18f","datavalue":{"value":{"amount":"+0.7604013681411743","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":"Q634249$ABC7187D-1089-473D-A468-831A6F379A6F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Reconstructing orthogonal polyhedra from putative vertex sets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Reconstructing_orthogonal_polyhedra_from_putative_vertex_sets"}}}}}