Shape up or guard up

Probability Level 1

Suppose a museum in the shape of a polygon can be guarded by a single guard. Does this imply the museum is convex?

Detail s: A point $P$ in the museum is visible to a guard if the line segment from the guard to $P$ lies within the triangle (or along the boundary).

See Guarding a Museum for details on guarding a museum.

No, the museum is not necessarily convex. Not enough information. Yes, the museum is always convex. The museum is convex and must be a triangle.

3 solutions

Mei Li Staff
Mar 12, 2015

The museum does not have to be convex. For example, two triangles meeting at a single vertex can be guarded by one guard sitting at the vertex, but the two triangles together give a non-convex museum.

Wwt Manahan
May 15, 2015

Imagine a spikey museum, like this:

This guard can see everywhere in the museum, yet it is not convex. So the museum certainly doesn't have to be convex. However, it doesn't have to be not convex, since one guard could certainly guard, say, a triangular museum. Therefore, it is impossible to make assumptions whether the museum is convex or concave.

this is a much better example than the prior. how can a single person continually monitor a location in front of and behind? I was on the same path as you but I didn't think about the spikes. great job!

michael bye - 5 years, 6 months ago

Laura Gao
Mar 27, 2018

This shape is not convex, but a guard standing anywhere along the red dotted line will be able to guard the whole museum.

Shape up or guard up

3 solutions

0 pending reports