{"entities":{"Q705130":{"pageid":706979,"ns":120,"title":"Item:Q705130","lastrevid":63665412,"modified":"2026-04-11T14:43:09Z","type":"item","id":"Q705130","labels":{"en":{"language":"en","value":"Hierarchical decompositions and circular ray shooting in simple polygons"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2130997"}},"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":"Q705130$6EFEAC08-645D-4BF9-85B0-BD706F959D4E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7abfb3c6c598f589d5ccb93a6fc2bba82fb79632","datavalue":{"value":{"text":"Hierarchical decompositions and circular ray shooting in simple polygons","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q705130$59D3D813-39E6-4BCF-BCE0-61C787ED98BC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d33defb7e639c9dd11713b0d7804b6a9825155de","datavalue":{"value":"1075.65028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705130$7EF8C98A-0981-48AE-BC82-617D623AF460","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3ba5aa216f2d6584c6b877fd61e686d62b452d3e","datavalue":{"value":{"entity-type":"item","numeric-id":331367,"id":"Q331367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705130$D02FD1F6-D7B3-446E-A0CF-3ACE8568AC3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0dd41e0c9fd856e61a9a7227322992849270ab58","datavalue":{"value":{"entity-type":"item","numeric-id":293305,"id":"Q293305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705130$DCEE4353-130D-4F3D-9383-F3DDE84F8CD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9159f9007a22ed652d25e1f9c881c937c2a0cf84","datavalue":{"value":{"entity-type":"item","numeric-id":598229,"id":"Q598229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705130$1BD28104-5E7C-4ED8-93F7-5857EBEF3A89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fe51ab34fca76d52c385a1ca93b7dc29b1c6d1a2","datavalue":{"value":{"entity-type":"item","numeric-id":1175645,"id":"Q1175645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705130$47AC42C5-F6BA-469D-BDFE-65B450889364","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705130$79F93411-5FBB-4DC9-BCC9-B36F76684636","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e1590bd54b214ce942d11ecbfe0ede26ab9b97ec","datavalue":{"value":{"time":"+2005-01-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q705130$A8F9A907-4C89-462C-9E71-3DB9DE251FBC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"62cf87d6d968c210b44b272db5b981eca2c705b5","datavalue":{"value":"A new hierarchical decomposition of a simple polygon is proposed, whose regions have at most three neighbors. The construction of the hierarchy of logarithmic depth and linear size is based on the trapezoidal map (vertical decomposition) of the polygon. As application, circular ray shooting queries in a simple polygon of \\(n\\) vertices can be answered in \\(O\\left( \\log ^{2}n\\right) \\) query time, with \\(O\\left( n\\log n\\right) \\) space and \\(O\\left( n\\log ^{2}n\\right) \\) preprocessing time, improving over previous results in the literature. A data structure with optimal query time \\(O\\left( \\log n\\right) \\) \\ and optimal size \\(O\\left( n\\right) \\) is obtained for fixed-radius circular ray shooting.","type":"string"},"datatype":"string"},"type":"statement","id":"Q705130$62468C80-609D-4F99-BD7B-155879B6085B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705130$BA796F14-9093-4F52-883F-ABE7418586ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2762df744fec88c5da60f696833f02907bd4417a","datavalue":{"value":"52B55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705130$3D9672B2-4ECA-48A4-B1EA-4DA951A5A1EB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"10a5f8d05e76666f92af84294349afdf53f6199b","datavalue":{"value":"2130997","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705130$47D12C0F-133E-4701-9BDD-4CD2B858C1B1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b507b3e814312824491e1ff4eb0dd4f684db6544","datavalue":{"value":"hierarchical decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q705130$0722F227-1812-429A-BFBC-98BE7029FC02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c25bc710e4a99b4ad5c06b7d722ebbdb9259ca1e","datavalue":{"value":"data structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q705130$2F3C1D25-8461-4867-8F37-498F245EAAAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09b6f84ba9ce92211b37dee6c8a56f30afe157b2","datavalue":{"value":"circular ray shooting","type":"string"},"datatype":"string"},"type":"statement","id":"Q705130$B1C3AD49-61B3-4714-9B68-5C322EC0B623","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b198546508854bcc521c452e3e0681a16812ba9","datavalue":{"value":"polygon","type":"string"},"datatype":"string"},"type":"statement","id":"Q705130$E9C6D288-D834-4F6C-ADEF-DB960749BD8D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a3503fd4727f823d79ecdba2b57dbab0be832911","datavalue":{"value":{"entity-type":"item","numeric-id":1305496,"id":"Q1305496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705130$A656A9B8-6DE7-46BF-9697-01AA3C8FCF97","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":"Q705130$04E9B645-9C0A-4860-861E-488B5125C9F4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"037e2cdc60fe32d563e28903a60cf0e190d19d80","datavalue":{"value":"https://doi.org/10.1007/s00454-004-1098-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q705130$4DAC9C8C-00FF-4A1B-8F45-7FF1207643C4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8db6ff0e026748906143c45e80a3459b10b40507","datavalue":{"value":"W2165671244","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705130$97AA765F-4C7E-4D30-B96A-88993717CFAF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"64281018f26cbaf4921ba0b0413cd40a335663f1","datavalue":{"value":"10.1007/S00454-004-1098-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705130$2757AF34-20D2-4B45-A369-6526DB1AD343","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d163d20c29178ddcc3188c782403b7aca0673aaa","datavalue":{"value":{"entity-type":"item","numeric-id":4036602,"id":"Q4036602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a556c04470142d0c1d21917289edbfe1b0230bf","datavalue":{"value":{"amount":"+0.8911538","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705130$67C3D8F9-24C5-45F9-9464-63C773CAB99D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79ce5dbe49307348bf577b41504d222cb0c6ffdd","datavalue":{"value":{"entity-type":"item","numeric-id":1330785,"id":"Q1330785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a556c04470142d0c1d21917289edbfe1b0230bf","datavalue":{"value":{"amount":"+0.8911538","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705130$1FB3F6E9-D2C4-4088-83C4-B441BEDD9A8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f99268087d64b10dbc1ee0483d486da3f9f9585","datavalue":{"value":{"entity-type":"item","numeric-id":685183,"id":"Q685183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aab945beee448aeee12e538c3660c31bf91c1609","datavalue":{"value":{"amount":"+0.87600744","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705130$409ADEC0-0E17-4E7B-9DD1-AFF2A652DD2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99727d4fdb5024ce122a56d4ea9306d7f1c4a436","datavalue":{"value":{"entity-type":"item","numeric-id":5370699,"id":"Q5370699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"074c0e70490d0385a978f0242a17e0adb0c9e0e2","datavalue":{"value":{"amount":"+0.86467457","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705130$7A6B5727-4F42-4D5D-81AB-6641B0C4D2EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d5988f5304907f190716502043d58e28e4330b8","datavalue":{"value":{"entity-type":"item","numeric-id":3143300,"id":"Q3143300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"074c0e70490d0385a978f0242a17e0adb0c9e0e2","datavalue":{"value":{"amount":"+0.86467457","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705130$6FE8F7B0-040A-4C6E-92EF-8DF067EDF5DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"227fb39440482dc2dec2bea3efa8d9d23d42b456","datavalue":{"value":{"entity-type":"item","numeric-id":4875447,"id":"Q4875447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"676590a0ae43d8d28f891e0797b4fd986ef8a356","datavalue":{"value":{"amount":"+0.85937035","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705130$330E8CE0-BBFA-49C1-9AFF-07E2E55BA713","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85da3652217a4c5024bc7beb37ef1f1c87f0e091","datavalue":{"value":{"entity-type":"item","numeric-id":3140428,"id":"Q3140428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5956faba74be55d8c8d8e0f74bc71eaae0836dc5","datavalue":{"value":{"amount":"+0.8571186","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705130$EA6D6F86-EC86-4C27-8756-5A327BF52ED7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c2318e62593447681a3a3e416842d357aa15c78","datavalue":{"value":{"entity-type":"item","numeric-id":3837381,"id":"Q3837381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b46a8828bff538e02cd290456bb06644f1c2a551","datavalue":{"value":{"amount":"+0.85596836","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705130$F3E55452-74E2-426E-B332-1A5BD17C61C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2c46a224d0197f92640855374ad13816bc93829","datavalue":{"value":{"entity-type":"item","numeric-id":2261573,"id":"Q2261573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e43793b8f072f057ae2b1821f66f0454692a9604","datavalue":{"value":{"amount":"+0.84471977","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705130$5E5A297A-AC30-45A9-9915-67EB4983638E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6562252c5947f9daebda938cce3dc677b05fc37","datavalue":{"value":{"entity-type":"item","numeric-id":2842161,"id":"Q2842161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e43793b8f072f057ae2b1821f66f0454692a9604","datavalue":{"value":{"amount":"+0.84471977","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705130$6A4032E9-8EE5-4670-98BA-4FE224EA62A7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Hierarchical decompositions and circular ray shooting in simple polygons","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Hierarchical_decompositions_and_circular_ray_shooting_in_simple_polygons"}}}}}