In this paper, we address the problem of autonomous exploration of unknown\nenvironments with an aerial robot equipped with a sensory set that produces\nlarge point clouds, such as LiDARs. The main goal is to gradually explore an\narea while planning paths and calculating information gain in short computation\ntime, suitable for implementation on an on-board computer. To this end, we\npresent a planner that randomly samples viewpoints in the environment map. It\nrelies on a novel and efficient gain calculation based on the Recursive\nShadowcasting algorithm. To determine the Next-Best-View (NBV), our planner\nuses a cuboid-based evaluation method that results in an enviably short\ncomputation time. To reduce the overall exploration time, we also use a dead\nend resolving strategy that allows us to quickly recover from dead ends in a\nchallenging environment. Comparative experiments in simulation have shown that\nour approach outperforms the current state-of-the-art in terms of computational\nefficiency and total exploration time. The video of our approach can be found\nat https://www.youtube.com/playlist?list=PLC0C6uwoEQ8ZDhny1VdmFXLeTQOSBibQl.\n