Diffuse reflection radius in a simple polygon

DOI10.1007/978-3-319-08783-2_21zbMATH Open1352.68267arXiv1402.5303OpenAlexW1538189031MaRDI QIDQ727965FDOQ727965

Eli Fox-Epstein, Csaba D. Tóth, Andrew Winslow

Publication date: 21 December 2016

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: It is shown that every simple polygon in general position with $n$ walls can be illuminated from a single point light source $s$ after at most $lfloor(n-2)/4floor$ diffuse reflections, and this bound is the best possible. A point $s$ with this property can be computed in $O(nlogn)$ time. It is also shown that the minimum number of diffuse reflections needed to illuminate a given simple polygon from a single point can be approximated up to an additive constant in polynomial time.

Full work available at URL: https://arxiv.org/abs/1402.5303

zbMATH Keywords

visibilityart gallerylink distance

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• A linear worst-case lower bound on the number of holes inside regions visible due to multiple diffuse reflections
• Maintaining visibility of a polygon with a moving point of view
• Diffuse reflection diameter in simple polygons
• A linear time algorithm for minimum link paths inside a simple polygon
• The Complexity of Diffuse Reflections in a Simple Polygon
• Polygonal Rooms Not Illuminable from Every Point
• Visibility Algorithms in the Plane
• Optimal shortest path queries in a simple polygon
• Matrix Searching with the Shortest-Path Metric
• Computing the geodesic center of a simple polygon
• A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
• A Helly-type theorem for intersections of compact connected sets in the plane
• An Optimal Algorithm for Finding the Kernel of a Polygon
• A Helly-type theorem for simple polygons
• SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS
• Visibility queries and maintenance in simple polygons
• Efficient visibility queries in simple polygons
• Weak visibility queries of line segments in simple polygons
• Computing the L 1-diameter and center of a simple rectilinear polygon in parallel
• Computing the link center of a simple polygon
• An \(O(n\log n)\) algorithm for computing the link center of a simple polygon
• Diffuse reflection diameter and radius for convex-quadrilateralizable polygons
• Algorithms for Computing Diffuse Reflection Paths in Polygons
• Some Unsolved Problems in Plane Geometry
• Computing the L 1 Geodesic Diameter and Center of a Simple Polygon in Linear Time

Cited In (2)

• Reflective guarding a gallery
• ПОЛУТЕНЬ В ТЕПЛОВОЙ ДИФРАКЦИИ НА МНОГОУГОЛЬНИКЕ

This page was built for publication: Diffuse reflection radius in a simple polygon

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q727965)