{"entities":{"Q2495948":{"pageid":2506691,"ns":120,"title":"Item:Q2495948","lastrevid":49869469,"modified":"2026-01-11T11:20:19Z","type":"item","id":"Q2495948","labels":{"en":{"language":"en","value":"Octrees with near optimal cost for ray-shooting"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5037826"}},"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":"Q2495948$D2705FB7-2F90-4340-849D-1AF953C326D2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"33134d725187c1e29fa42ea622a351b697086516","datavalue":{"value":{"text":"Octrees with near optimal cost for ray-shooting","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2495948$1A4A05B4-A160-44C0-893A-CEC01B1F5A5A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4f19b74916db0deebe783a94d86cc57289ccaf5a","datavalue":{"value":"1101.65019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2495948$8F8EDD3B-A9B3-4041-8B3F-F1307EFBAD3E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"56d5e6541ef9a0df9ab3690b4607cf1918f3611b","datavalue":{"value":{"entity-type":"item","numeric-id":420576,"id":"Q420576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2495948$409C4770-AFE8-4DF2-ABFC-73A61ABD578A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fc7f5fc236fcded234f18e2d4a40c6d8646c4022","datavalue":{"value":{"entity-type":"item","numeric-id":170474,"id":"Q170474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2495948$DC9E1B7B-595A-4847-B3D6-87A0B008E80D","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":"Q2495948$09871550-2A11-41AB-91E2-BEA547973694","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9e66041b42d053f5f2145cbbf08b1b29afba170b","datavalue":{"value":{"time":"+2006-06-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":"Q2495948$001CB47F-F28B-4F7E-853F-E711025CE561","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"52cdc1869627a5ed4d2c2b638f9183e7f7035b9b","datavalue":{"value":"The ray-shooting problem consists in finding the first object in the scene which is intersected by the given ray. To increase the efficiency of visibility algorithms, which are based on ray-shooting, a suitable space decomposition of the scene is used -- a quadtree in the plane or an octree in the space. The authors are interested in the construction of trees with a guaranteed approximation ratio without increasing the cost too much. The suggested procedure constructs the octree with cost \\(O(M)\\), where \\(M\\) is a lower bound on the cost of any tree for the given scene.   Here, the scene that consist of solids represented by their boundaries are considered. The boundaries of the solids can be subdivided into elements of constant combinatorial complexity. In the article, the effect of rebalancing the tree on the cost measure is examined, too. Adjacent cells of the balanced tree have the same size. The authors prove that rebalancing only increases the cost by a constant multiplicative factor.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2495948$1F2B59C5-FA8C-43C6-9E70-D402CA8DE176","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4477e8d68582d98ecbcdc7eba969a5512a4a4bbc","datavalue":{"value":{"entity-type":"item","numeric-id":591762,"id":"Q591762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2495948$44180E15-AC82-4DA7-9303-43A91BB3741B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2495948$021850D6-5469-4096-BC2A-325D1FB6727B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2495948$B814C195-6367-4285-804C-691821FF4B61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ab7a0d2add14e0dbd91ec8ae1d32a5bb94f2fb34","datavalue":{"value":"68U10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2495948$B178D066-2AD2-4A00-91BB-B988E151DFA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2495948$F577D12A-FA22-43D8-A531-88B9707D1D68","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"40a390cc24b48947c0ac155cdb210f2cbc165991","datavalue":{"value":"5037826","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2495948$4C5A0BA7-2760-46C0-98BC-7BD12CD99975","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"709c8dd5c89f5e072db3915362a97249a6e323e7","datavalue":{"value":"ray-shooting","type":"string"},"datatype":"string"},"type":"statement","id":"Q2495948$EF309C33-BF4E-488C-B6A2-EEF1C2CB6C97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7bfd605e8d1eec2e403cfe1b9f8fb6385b43b4a0","datavalue":{"value":"visibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q2495948$9AA8A0B6-66C5-489E-8F06-C65239F1124A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c27024bc3112e6fbf1cca0a9a4aacb8e7e4a77e0","datavalue":{"value":"optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2495948$59FB67F7-B3FE-4117-91B8-25DC4B8EFB99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"828013a23135c69163f579eac4ae71a750c0fb9e","datavalue":{"value":"space decompositon","type":"string"},"datatype":"string"},"type":"statement","id":"Q2495948$160F21BD-DC94-4DEB-A547-A3F03B0A7D45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d084118b96b2d4096aadcf8cd6903f77f9f90edf","datavalue":{"value":"quadtree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2495948$8338FD0C-2DDD-40BB-8D5E-B60D979729C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61aae68d8de6eaab20d24257084645a976cb12e5","datavalue":{"value":"octree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2495948$9D8D067F-2FD1-40A4-8235-51D5BB81E036","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1bf370948f44842238b034cfcb3554331db8ba6a","datavalue":{"value":"cost model","type":"string"},"datatype":"string"},"type":"statement","id":"Q2495948$717CAAEA-480F-40C1-9285-D4E3531581D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f166caa50b408603b2527f6a2f2404133f758fb","datavalue":{"value":"cost prediction","type":"string"},"datatype":"string"},"type":"statement","id":"Q2495948$171CC425-750E-446C-99D5-7E72BBB00A48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21d2a02ef48de9755cdcb0ff0eb3b2a0c9408b3a","datavalue":{"value":"average performance","type":"string"},"datatype":"string"},"type":"statement","id":"Q2495948$54033335-AF9A-417F-8481-8F81CD5EAF1A","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":"Q2495948$1FFB6EA4-F239-4805-95A4-67CC928CCDC5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"16bd13659263530f161a94412183bbf24fc3dbe0","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2005.09.003","type":"string"},"datatype":"url"},"type":"statement","id":"Q2495948$28FCE1DA-0F5F-4D80-A37B-691E0E8723C2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b78ffe9f67ab5cba6741b87886a7cee3314dd830","datavalue":{"value":"W2002880487","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2495948$2199CC60-950A-4BB9-80BA-C6CA59122BF7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d413589af8d1f36740acb59fcc7956d34c7d208","datavalue":{"value":{"entity-type":"item","numeric-id":4557565,"id":"Q4557565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2495948$EDD11A9F-12C3-4987-B386-AE15C3AB07CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3aaadf2d65ee248033a92f88b196771ed8cdb9a2","datavalue":{"value":{"entity-type":"item","numeric-id":1775782,"id":"Q1775782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2495948$CF8F4F88-654E-482C-B293-C54FBCD4E015","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df0b2f51ab65003c775c482790b57883e51072a8","datavalue":{"value":{"entity-type":"item","numeric-id":1293672,"id":"Q1293672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2495948$D70E9678-72E9-4705-A047-AEC432527F5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d0c4a164492abc3b71cf04f246ef23bdc5267a4","datavalue":{"value":{"entity-type":"item","numeric-id":3736455,"id":"Q3736455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2495948$2FD728DA-BE80-462C-91AF-62F5139A0A72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6339a6376212f46a33613e79a98c148930202a7c","datavalue":{"value":{"entity-type":"item","numeric-id":4692930,"id":"Q4692930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2495948$FE4C2E0E-AA41-4909-80B0-94B043A096B5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1eb64a425c032a61dab22b76051ab425062f01ed","datavalue":{"value":"10.1016/J.COMGEO.2005.09.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2495948$A2344466-FFD6-499A-BD67-633D06957CD3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98086741c9fd4c34de7ae19cfaf7b8b317d57469","datavalue":{"value":{"entity-type":"item","numeric-id":5901655,"id":"Q5901655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"213512f74a7a2add3b50fc83096ec42dc2e0020f","datavalue":{"value":{"amount":"+0.9049626588821412","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":"Q2495948$534543DB-4857-428F-9607-77C0E94D2CEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bad60bb61421763c4a69708f0896f3b6d9f2810c","datavalue":{"value":{"entity-type":"item","numeric-id":1775782,"id":"Q1775782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67c0cf0b1447b300400fa106c8d110f0dd2eff9a","datavalue":{"value":{"amount":"+0.8615236282348633","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":"Q2495948$4DD24FE5-2010-4371-97EF-30381BCAED09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ca2a2f85994aeaaeeea2fbb8e20caa98dfc7429","datavalue":{"value":{"entity-type":"item","numeric-id":5361627,"id":"Q5361627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e5314abea515680009b7e5d1cdde99f2937fec2","datavalue":{"value":{"amount":"+0.8440124988555908","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":"Q2495948$AB13C7E1-EB88-495B-A24A-6A1D37200F63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a989d8323787688f8dd7c39aaa64337b416aa4c9","datavalue":{"value":{"entity-type":"item","numeric-id":4557565,"id":"Q4557565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ea29713be78dbc6af65b7223c9dc92d2656416e","datavalue":{"value":{"amount":"+0.823898434638977","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":"Q2495948$C11B7F8A-CC60-4AF2-A29A-AC6260FB53FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6aee7d8adbd0d096a6eef5227d53c800e713653","datavalue":{"value":{"entity-type":"item","numeric-id":2495947,"id":"Q2495947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ca232367eb2abf60781b2f045222d53498b4046","datavalue":{"value":{"amount":"+0.8108940720558167","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":"Q2495948$211E3F2B-9DA2-47EA-8587-75658813386D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2495948","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2495948"}}}}}