An Algorithm for Illuminating n n Nonoverlapping Circular Discs’ Boundaries on the Plane with Application to Tree Stem Illumination Problem

Phapaengmuang Sukkasem, Supanut Chaidee, Watit Khokthong · 2025

Read An Algorithm for Illuminating n n Nonoverlapping Circular Discs’ Boundaries on the Plane with Application to Tree Stem Illumination Problem by Phapaengmuang Sukkasem, Supanut Chaidee, Watit Khokthong (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-20440.txt.

Introduction

Phapaengmuang Sukkasem, Supanut Chaidee, and Watit Khokthong solve a lighting geometry problem in 2025. Given flat discs that do not overlap, where can a camera sit so its light reaches every disc's full rim? The puzzle has a practical twin: placing laser scanners to light tree trunks in a forest.

Their method meshes a special triangulation for circles with slices cut by tangent lines. Where the slices overlap, a camera can see all rims at once. Tests on random disc layouts confirm the regions work. The result could guide how many scanners a forest survey needs and where to stand them.

Catalog record

CREATORPhapaengmuang Sukkasem, Supanut Chaidee, Watit Khokthong
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-20440

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Algorithm for Illuminating n n Nonoverlapping Circular Discs’ Boundaries on the Plane with Application to Tree Stem Illumination Problem Phapaengmuang Sukkasem, Supanut Chaidee, Watit Khokthong Abstract Given a set of n n nonoverlapping circular discs on a plane, we aim to determine possible positions of points (referred to as cameras) that could fully illuminate all the circular discs’ boundaries. This work presents a geometric approach for determining feasible camera positions that would provide total illumination of all circular discs. The Laguerre Delaunay triangulation, coupled with the intersection of slabs formed by the boundaries of circular discs, is employed to form the region that satisfies the given conditions. The experiment is conducted using a set of randomly positioned circular discs on a plane. This study has the potential to address the issue of illumination in forests by utilizing a LiDAR camera to determine the possible number and placement of cameras that can effectively illuminate trees within a forest. keywords Terrestrial Laser Scanner, Illumination Problem, Slabs \FrontMatterExtraVskip 0.0pt \MSC 52C30, 52C35, 68U05 1 Introduction In our everyday observation, as well as in mathematical views as rooms or open areas with obstacles, we have the challenge of identifying the regions to circumvent obstructions in the visual field. From a mathematical perspective, the illumination problem is well established in discrete and computational geometry 13 . The main issue of illumination problems 23 is to find the least number of lighting points to obtain the highest illumination efficiency 20 and to place the lighting source so that it can illuminate the area or object 20 . There are widely known problems in the illumination problem, such as the Art Gallery problem 19 20 12 , the Guarding problem 11 2 , and the floodlight illumination problem 6 7 . In various conditions for illumination, the lighting source that is positioned can be projected to test the efficiency. A practical example of the challenge of illumination is the use of LiDAR (Light Detection and Ranging) sensors to illuminate forest structures for environmental research 15 . Forest practitioners have utilized the LiDAR 5 and camera sensors by the structure from motion to illuminate the forests. Focusing on the LiDAR, regarded as a light source capable of emitting illumination in all directions, the challenge lies in identifying the optimal position for the LiDAR laser scanner to maximize the capture of forest structural information. Recent studies focused on the suggestion of the use of terrestrial laser scanner (TLS) with forest. A study in Abegg et al. 1 , investigated the impact of different patterns of placement of scanners on visibility within forest stands when using terrestrial laser scanning. By simulating various scanning patterns and positions, the study demonstrated that the arrangement and number of scanning locations significantly influence mean visibility. Another study by Wilkes et al. 24 discussed the use of TLS to capture detailed forest structure data on extensive plots. The study recommended a systematic grid pattern for the scan position locations, highlighting the effectiveness of a 10m×10m grid in achieving uniform point distribution. The challenge of non-detection in single scan TLS of forests is addressed in a study from 2019 16 , which can miss some tree stems or other vegetative parts that are obscured by others. It introduced a new estimator in terms of marked point pattern of trees that compensates for these non-detection results, by considering different detection rules, which model partial or nearly full or visibility of a standing tree. The study in 2020 17 proposed an Iterative-Mode Scan Design for TLS in forests to minimize occlusion effects and improve accurate tree attribute estimation. The method evaluates the potential location for the scan using a PoTo index and the cumulative degree of ring closure (CDRC) to enhance the completeness of the scan, particularly in dense stands. Although the previously mentioned literature has suggested basic strategies for gathering tree-root information from TLS LiDAR, the specific procedure for determining the optimal placement of the active sensor remains improperly explored. To model this problem mathematically, we can represent the cross-section of the trees as a set of circles, with the TLS LiDAR serving as the emission light source. We aim to identify the optimal positions for TLS LiDAR to effectively illuminate a specified set of circles that can represent tree stems and to minimize the number of sources while maximizing the illuminated area. The study of Tóth 22 explores the illumination of convex discs and explains how a set of n circular discs can be illuminated by 2n points. Then there is more study of scenarios where circles overlap or are centered on a line. The concept of a generalized Voronoi diagram is used to describe how vertices can illuminate the corresponding arcs of a circle. Theorems are presented to establish upper bounds for the required number of lighting points, affirming the sufficiency of 2n points, and suggesting \max(2n,4n-7) points as necessary for nonoverlapping open convex discs. Those propose more results and combinatorial aspects in the art gallery problem in point guard and edge guard 20 18 . In this paper, we present a geometrical approach to ascertain the locations of light sources required for the total illumination of a collection of circles, guaranteeing that each circle is entirely illuminated by the sources. A slab characterized by a region bounded by parallel lines formed by two adjacent circles will be investigated to establish the feasible region for the placement of light sources. We prove the geometrical properties of intersecting slabs, then utilize these areas as potential locations for source placement, and propose an algorithm that addresses the problem. Subsequently, we conduct experiments to determine the optimal scenario using ideally generated data comprising both identical and varied circles. We also use artificial trees and utilize LiDAR to illuminate these trees, so obtaining the illuminated region serves as validation from the computations to quantify the accuracy from the ideally generated data. This paper is organized as follows. The introduction includes a related review on the research topic. In the second section, we provide the basic background in computational geometry, which we have used in this study. In addition, we formulate the problem to tackle in this part. The geometrical properties of the illuminating region will be investigated in Section 3, including an algorithm to locate the illuminating location. In Section 4, we perform experiments to verify the proposed algorithm. We finally conclude our study in the last section of this paper. 2 Preliminaries 2.1 Background in Computational Geometry The convex hull 9 of a set S , denoted CH(S) , is the smallest convex set that contains S . It is the intersection of all convex sets that contain S , i.e., for any \alpha\in\Lambda and C_{\alpha} a convex set covering S , CH(S)=\bigcap\limits_{\alpha\in\Lambda}C_{\alpha} . There are several algorithms to compute the convex hull from a set of finite points on the plane, such as divide and conquer. The time complexity of the convex hull algorithm is known to be O(n\log n) . A set of points p_{i}\in P where i=1,2,\dots,n on a convex hull segment of a convex set S is visible 10 to a light point q if and only if there exists a non-crossing line

Read the complete text