2D Visibility

2D Visibility

Applications

• Game Engines
• AI Engines
• Automated warcrafts
• Security Devices
• Cameras / Videography
• Placement of sensors
• Solar Panels
• Many more..

2D Visibility

Optimization

With one source

2D Visibility

Area Calculation

2D Visibility Optimization

Steepest Ascent

2D Visibility - Optimization

Simulated Annealing

2D Visibility

Optimization

With multiple sources

2D Visibility

Art Gallery Problem

Proposed by Victor Klee in 1976, this problem still stays as one of the most studied and researched problems in combinatorial optimization

How many lights would we need to light up an art gallery?

Yes! Its 4!

NP-HARDNESS

Reducing to Set Cover

Draw lines every vetex to another,

Unless they go outside

Parts Visible from Vertex A

Parts Visible from Vertex B

Parts Visible from Vertex C

This is exactly

Set Cover

Hence, Art Gallery Problem is NP-Hard

Chvátal's Theorem A.K.A.

Art Gallery Theorem

Václav Chvátal

[n/3] guards are always sufficient and sometimes necessary to guard a simple polygon with n vertices.

Assumptions

1. Art Gallery is considered as a simple polygon.
2. There is a single room, with no divisions or partitions in between.
3. The room is assumed to have finite sides

Art Gallery Theorem

PROOF

In three steps

1. Polygon Triangulation
2. Graph 3-Coloring
3. Recognize Minimum Occuring Color

Example Room

Polygon Triangulation

3-Coloring

Recognize Minimum Occuring Color

References