Simple solution: stop using weirdly shaped museums
@Alucard-gt1zf5 жыл бұрын
Ailis Catach then the museum would be empty
@nyesimpson87745 жыл бұрын
Alucard how exactly?
@Alucard-gt1zf5 жыл бұрын
Nye Simpson would be a really boring museum without any large exhibits that don’t block the view
@KrisMcCool5 жыл бұрын
Sounds about right
@dfferentpoint5 жыл бұрын
It's atr
@sipinosapa Жыл бұрын
No matter how many guards you put in a room. Nothing can stop a four man ECM rush.
@miraijfish Жыл бұрын
Just watch the lazers
@Lopeped-Cring Жыл бұрын
Except for that one guy that gets meleed by a guard, instantly killing them and launching them halfway across the gallery
@skell6134 Жыл бұрын
@@Lopeped-Cring Just have one guy with Inspire for that case,lol You dont exactly need low concealment build to do ECM rush XD
@EEEEEEEE Жыл бұрын
E
@samuellinn Жыл бұрын
@@skell6134 Inspire doesn't work during stealth btw. Me and my friend learnt that the hard way trying to defy gravity.
@Devlin201020115 жыл бұрын
“Assuming your guards have 360 degree vision and can only be place in corners” why? Why would I assume any of that?
@Blox1175 жыл бұрын
be silent comrade, we do not discuss such unimportant matters here.
@antimatter23765 жыл бұрын
well he did mention it'd be better to use 360 degree cameras but that he was sticking with guards. and hes saying only at corners so that the proof is a lot easier and to just have a solution
@d0nnyr0n5 жыл бұрын
@@somerandomguyontheinternet9100 He said "at once" as in: they have to be able to see everything at any moment.
@kuhmuh23575 жыл бұрын
welcome to math
@RedFox-dj7di5 жыл бұрын
@@kuhmuh2357 ya bro
@rexinkognito27405 жыл бұрын
one operating the cameras
@fernando471805 жыл бұрын
I'm not sure a single guard would be able to pay attention to, say, 50 cameras simultaneously, though
@rexinkognito27405 жыл бұрын
@@fernando47180 give him cocaine
@tdoubledub15 жыл бұрын
@@fernando47180 who said 50? just =>n/3
@teancrumpets56855 жыл бұрын
One operating cameras and one on the ground to respond quickly, using radios
@akashchoudhary81625 жыл бұрын
@@fernando47180 One guard operating 50 cameras with shape detection software
@centro.4k5 жыл бұрын
"My job gets me really dizzy." "What? What do you do?" "Oh, I'm just a 360° security guard." "How is that possible?" "I spin." "How does spinning... Oh.. That must suck." "No not really I love my job, it spins in the family."
@x_sphinz29824 жыл бұрын
This comment not having a reply after months is completely understandable.
@thelizardpalace45974 жыл бұрын
You really threw a spin on that
@thefierypaladin1264 жыл бұрын
Gyro be all
@espressocookie89654 жыл бұрын
*Spins rapidly*
@chrishansen18424 жыл бұрын
@@x_sphinz2982 look at what you've created.
@airmanon7213 Жыл бұрын
This makes me wonder how different the problem would be if the guards could be placed in places other than the vertices, *but* they have a limited range of vision of a given radius.
@ifroad33 Жыл бұрын
Im guessing you could draw imaginary intersections points by extending all vertices to a huge length, and look at where each and every one of these lines intersect. These would be the new points of interest since they tell us where we can get more information. For the radius thing I have no idea where to start lmao
@airmanon7213 Жыл бұрын
@@ifroad33 Good point.
@EEEEEEEE Жыл бұрын
E
@daniellucas5522 Жыл бұрын
Very - even just the question of how many you need to cover a circle is quite complex for small vision ranges.
@evank37185 жыл бұрын
Really thought you were going to triangulate that triangle into a Triforce. Missed opportunity
@selectivepontification87664 жыл бұрын
That would be cute but that goes against the principles shown in the video
@Anikin3-3 жыл бұрын
@@selectivepontification8766 YoU mUsT bE fUn At PaRtIeS
Жыл бұрын
@@selectivepontification8766Not sure. The induction would still work. It would just be needlessly complicated.
@EEEEEEEE Жыл бұрын
E
@zachstar5 жыл бұрын
Something I didn't mention but wanted to at least say here is that for galleries in the shape of an 'orthogonal polygon', where every corner makes a 90 degree angle (or 270 if we're talking internal angles) then the upper limit is n/4 (rounded down) instead of n/3. The proof is very similar so if you want a challenge you can give that a try.
@Leyrann5 жыл бұрын
I'd say that's pretty simple. Instead of making triangles, you make rectangles. Instead of 3 colors, you use 4 colors. You apply the same proofs used here - and you get n/4 rounded down.
@sugar2000galaxy5 жыл бұрын
you smart
@EEEEEEEE Жыл бұрын
E
@MsTwissy Жыл бұрын
Can you design a room made of mirrors that has a space that doesn’t get light?
@popeallahsnack-bar9804 Жыл бұрын
@@MsTwissy Yeah, a room full of mirrors with the lights off
@Some__Guy4 жыл бұрын
The thing with Ocarina's stealth section, is that it could have been easily been done with *one* single guard, who just guards any single choke point that you HAVE to go. Like, with that first square with the two fountains, just have someone lean against the wall in the left corner. Boom, no way to get through without being seen. If you want to assume that they're preparing for an intruder who could actually attack them, just add a second guard in the same spot. The only reason you would need the entire area in LoS, would be if you wanted to... I don't know, stop some weird kid from vandalizing the fountains?
@EEEEEEEE Жыл бұрын
E
@randomdude91355 жыл бұрын
This reminds me of the illumination problem discussed in Numberphile
@aidarosullivan52695 жыл бұрын
Maybe because these two problems are basically isomorphic (same)? lol
@martiddy5 жыл бұрын
Me too, I thought it was the same problem
@planetdesign46815 жыл бұрын
They are kind of the same
@Scratchmex4 жыл бұрын
@@aidarosullivan5269 they aren't "isomorphic" they are equivalent.
@mhilmihamka4 жыл бұрын
@@aidarosullivan5269 it is similar, but not the same. Illumination problem defines walls (sides of polygon) as mirrors; it reflects light, whereas art gallery problem define its walls to be non-reflective.
@cd.s.82 Жыл бұрын
I watched this video twice 3 years apart, before taking a college-level discrete maths course and right after. Now, being able to understand the terminology and logic just made me appreciate this video that much more.
@MykhailoBazalii Жыл бұрын
So, I guess there is something much deeper in the video than what I saw in it. Because I did not take a course in mathematics
@EEEEEEEE Жыл бұрын
E
@Jetpans Жыл бұрын
Yea, im watching this after taking discrete maths aswell and it is nice to see all the proofs which I once did used in a problem. The induction explanation in the video feels backwards because formaly you first make a conjecture and then use the trivial case to proove the conjecture.
If there's no light source it is indeed very difficult to observe the entire room when it's closed off from the outside. That aside, the question was how many guards was required to observe the entire room at once, so whether or not a break-in is plausible is besides the point.
@LineOfThy Жыл бұрын
when did it ever mention that?
@dumb214 Жыл бұрын
No, the entire room has to be observed since they forgot to install a roof, so thieves can drop in and land at any location in the gallery from their helicopters.
@skell6134 Жыл бұрын
@@dumb214 Wouldnt be able to do that without breaking their legs tho ? Unless someone conviniently place stuff for them to land on tho
@sketchyth0ughts3995 жыл бұрын
You can have 10, 15 or even 20 guards in a room, cameras, sensors, tripwires and mines. But Snake will always find a way.
@jo_nm94845 жыл бұрын
😂
@catchara14964 жыл бұрын
SketchyTh0ughts da box
@notme8232 Жыл бұрын
Just don't put a cardboard box in the museum, and you'll be fine.
@drm.himself Жыл бұрын
Because he can reload saves
@catboy6451 Жыл бұрын
Snake sneaking in and seeing 4 well dressed men with clown masks
@itsraahul5 жыл бұрын
That's how you TEACH 😍 I can re-explain the whole thing without having to watch it ever again. Wish my math teachers were like you sir. Sad part is this isn't there for my syllabus 😣
@yousefmahmoud13585 жыл бұрын
approved.
@arsongamer15104 жыл бұрын
Your math teacher didn't make a lesson to be watched by thousands, they probably didn't even have the powerful video editing to assist in understanding
@EEEEEEEE Жыл бұрын
E
@TugiDeg Жыл бұрын
I go too far calculating the perfect preplanning of a heist in PAYDAY 2.
@CarlJohnson-cb9xm5 жыл бұрын
10:33 Minimum 2 guards are required here
@aasyjepale52105 жыл бұрын
right-most blue and top-most red or green
@skylark.kraken5 жыл бұрын
@@aasyjepale5210 We don't know for sure if the blue is able to see all of the bottom triangle (there may be a slither missing) as we aren't told exact lengths of the sides of the bottom right corner. Top green and the red below is a solution we know can be correct, also they're close enough to chat to each other.
@Banzybanz5 жыл бұрын
Prove it.
@CarlJohnson-cb9xm5 жыл бұрын
@@skylark.kraken hmmm
@jackkilduff41045 жыл бұрын
No shit sherlock
@cubiccalico50194 жыл бұрын
my first thought of triangulating a triangle was to use the bisector of one of its angles (splitting it into two, smaller triangles) until you mentioned that it's already a triangle and doesn't need to be split up. thank you brain for wanting everything to be complicated.
@bwpbwp96134 жыл бұрын
4:06 can definitely be done with 2 guards...just dont only place them at verticies. The figure can be adjusted slightly to make your point, but as it currently is shown you can put a guard on the bottom line between 2 of the upper point’s angles and the last guard where they can see the other point.
@C0nstellati0ns5 жыл бұрын
4:00 you can observe everything with 2 guards if they weren't in the corners
@jamesliu32955 жыл бұрын
Some of the middle triangle would be out of view (draw straight lines from corners)
@sugar2000galaxy5 жыл бұрын
actually no and i have proof *i got none but pretty sure im right my brain say so*
@Ahmet12345.5 жыл бұрын
true
@ringkichard5 жыл бұрын
This can be done with 2 guards in this case. Proof by example: Lets divide the room into a large rectangular area at the bottom of the picture, and the three triangular bumps at the top. Imagine three friends, each one standing at the top of a bump and looking down at the far wall. They see most of the gallery, but not all of it, and cannot see each other. Just to help with the explanation, imagine that the room is dim and the center friend turns on a flashlight, illuminating the center cone of view. The left friend, standing at the top of the left bump, can see part of the flashlight's beam. If the left friend turns on a flashlight, too, there will be a bright patch illuminated by both flashlights. That is the area that those two friends share and can both see. The same thing happens on the right. There is an area that the center and right friend share. If you put a guard in a shared area, the guard can see both of the friends that share the area. If you put one guard on the left and one guard on the right, those guards will be able to see all three friends and also the whole rest of the room. QED
@connorabraham34745 жыл бұрын
Even if they were in the corners u could still use 2
@zsivkovicsmate87474 жыл бұрын
1:16 "The art gallery problem is both easy, by easy I mean understandable, and also hard, I'll explain what that means later." We know what hard means it means hard
@obviouslykaleb79984 жыл бұрын
*lenny face*
@jayxi50214 жыл бұрын
4:07 You only need to, the line of the right side of the left triangle and the line of the left side of the middle triangle touch eachother inside of the polygone. Just put 1 guard at the intersection to watch over both the triangles.
@maxx-er3fj Жыл бұрын
Came here to say that, good spot
@noodle67 Жыл бұрын
The only issue is that they have to be placed on the corners :/
@simonwillover41755 жыл бұрын
Look at triangles that are covered by multiple guards in a color and in different colors. I think you could use patterns with shared triangles to optimize guard placement (by minimizing triangle sharage).
@willwu42304 жыл бұрын
5:50 This is handwavy, and wrong. Think of a polygon starting with a square of side length 1 and cut out a smaller square of length >0.5 from its top right corner. Let the bottom left vertex of the 1x1 square be A, its adjacent vertices be B & C, and let the bottom left vertex of the smaller cut-out square be A'. If you start with vertex A, which is 90 degree (less than 180 degree), you cannot directly connect B and C. When you "shift" BC and hit A', by connecting A and A', you don't get a 5-gon and triangle, but two 4-gons. This way, you'd need strong induction.
@xeogillis36664 жыл бұрын
4:07: In this case two guard are enough because of simple mathematical solutions. Since it is true you only need one guard for a normal surface you can start looking for them. So instead of seeing this as some kind of rectangle with three triangles, you can extend the legs of the triangles and if the legs overlap you can use that specifik region to place a guard. This guard will be capable of seeing the left triangle as well as the right.
@Glue_Eater06 Жыл бұрын
This being called The Art Gallery problem made me think this was about the hiest in Payday 2
@EelcoWind4 жыл бұрын
Shows shape: How many guards? Me: Two! Explains a lot of theory: We can prove at least 10/3 rounded down, thus 3. Me: ...Two! Informs: There's no algorithm that can prove the exact amount yet. Me: TWO! ... Two, 2... TWO! Z! [in Roman] II... TWO, dangit! Me disappointed...
@jacobjones70154 жыл бұрын
There is no efficient algorithm. There are algorithms that can solve it, but they start to take a very long time as the shapes get complex. Complex meaning you have no chance of solving them just by looking at them.
@jacobjones70154 жыл бұрын
@@Satheo05 Probably (long time since I watched the video), but that isn't the point. As the shapes become more complicated, they quickly are impossibly difficult to solve. Another example of a problem that seems simple but isn't is factoring primes. For example, can you figure out what two prime numbers multiplied together give you 10? It's pretty simple - 2 and 5. But we don't have an efficient algorithm to solve those problems. We can do it easily for small numbers, but not for large numbers. If you had a way to efficiently factor large numbers, you could easily make millions of dollars by showing the NSA or a large bank how.
@ZekuChanU3 жыл бұрын
Guard: “Why am I spinning in circles in the corner of the room???” Me: “Don’t worry about it, you are still getting paid”
@samnotloading61015 жыл бұрын
Payday 2 taught me everything i need to know
@earavichandran5 жыл бұрын
I am very jealous about you. You have potential and excellent explaining skills. Heartly congratulations. Your videos are awesome.
@metametodo5 жыл бұрын
Replying just to stress this more. Since the very first time I watched you I felt something different, more clear and objective explanations. Congratulations.
@zachstar5 жыл бұрын
Thank you!
@connorhorman4 жыл бұрын
Side note, you'd actually need to use strong induction to prove any polygon can be triangulated. In regular induction, you prove the theorem for n+1 given the theorem for n, n> some a for the inductive step. In strong induction, you prove for n+1, given a,a+1,a+2,..., for n>a, for the inductive step. For example, the shape you showed for n=5 needs n=3 and n=4. The proof for n=4 was not sufficient.
@erniesummerfield6472 Жыл бұрын
You know I often forget this guy used to do educational videos
@marc-andreservant2014 жыл бұрын
Slight sidenote: finding an efficient, polynomial-time solution to an NP-hard problem wouldn't just be a better algorithm. It would be a paradigm shift, a world-changing, million-dollar prize winning, revolutionary breakthrough that would change the future of computing, challenge our perception of proofs as a concept, earn you a tenured position at the prestigious university of your choice, and grant you everlasting fame.
@SeriousApache5 жыл бұрын
Guys, the thermal dr... Oops, wrong heist.
@piotr88e5 жыл бұрын
bain never shuts up
@marcusjakobsson43214 жыл бұрын
ah, i see you're a man of culture as well
@Krushking994 жыл бұрын
Donacdum
@destarker13404 жыл бұрын
Did anyone bring a medic bag?
@Solrex_the_Sun_King Жыл бұрын
Here's the solution to the problem given an example from ocarina of time: Go to the place at night and a guard will stop you in your tracks. Only 1 guard is needed. Now why they only have the night shift, who knows.
@yukkahiro Жыл бұрын
Creating perfect camera/guard system with no blindspots: Payday gang with loud approach:
@vinfamous92265 жыл бұрын
This has quickly become one of my favorite channels! Continue what you are doing, its awesome content!
@Mr5nan5 жыл бұрын
I thought you were gonna solve the NP hard problem, but I'm not disappointed 👍🏻
@mcmonkey264 жыл бұрын
Egg
@Dusk_Holloway5 жыл бұрын
At least 40 and they all get EOD suits an miniguns
@TheRedCap4 жыл бұрын
1AM KZbin is a magical place
@soupy589025 күн бұрын
Craziest thing happened for me; I was curious about writing up a program, inspired by playing lethal company, for pathfinding on levels/maps that were generated by linear walls, and also I was fixated on the idea of representing them in terms of seperate "cycles" to allow, and was trying to figure out how to even find A single path from any 2 points. I was reminded of this video somehow, and the triangulization argument after a break and some thinking literally solved most of the problem by translating it to a very-constrained travelling-salesman problem where the vertexs were the triangular regions and the edge relation was side-adjacency. So even if you didn't invent this stuff (I'm aware invent may or may not be the "correct" word depending on some philosophy stuff, but I don't care right now its late), you popularized it to reach my eyes and aid me in a different problem, so thank you zach.
@byronwatkins25655 жыл бұрын
You didn't actually show that an n-sided polygon can be separated into a triangle and an (n-1)-sided polygon; you stopped at n=6 and simply stated that it can be done.
@zygoloid5 жыл бұрын
Right, and this is essential. You can't three-colour the vertices of an arbitrary triangular plane graph. Consider a pentagon with one extra vertex at the center that connects to all other vertices: in a three-colouring, the middle vertex would be one colour, and the colours around the edge would need to alternate between the other two colours. Because there is an odd number of edge vertices, that can't happen so there is no three-colouring. You need to make use of at least one additional property of polygon triangulations for the result to follow. (Eg, the dual graph (excluding the "outside" vertex) is a tree, or equivalently cutting along any interior edge disconnects the polygon.)
@byronwatkins25655 жыл бұрын
@@zygoloid It isn't necessary to have a 5-way intersection. Label the corners clockwise 1,2,3,4,5. Connect 1-3 to form triangle 1-2-3-1. Connect 3-5 to form triangle 1-3-5-1. This leaves triangle 3-4-5-3... I believe this can always be done and I can conceive no exception; but it was not demonstrated.
@zygoloid5 жыл бұрын
@@byronwatkins2565 Right. Any triangulation of a polygon (such as your example) can be three-coloured. But that wasn't my point (nor yours, as I understand it). My point was that not every plane graph of triangles that covers a polygon is three-colourable (which my counterexample demonstrates), and the proof as presented, if correct, would apply to all such cases (because it didn't rely on any properties of triangulations of plane graphs that aren't properties of the more general case). Therefore the proof as presented is (slightly) incomplete.
@willwu42304 жыл бұрын
Besides the way he proves "n-sided polygon can be separated into a triangle and an (n-1)-sided polygon" is wrong.
@willwu42304 жыл бұрын
@@zygoloid The premise of the proof is a polygon. "A plane graph of triangles that covers a polygon" is not a polygon (like your pentagon example)---it has additional interior edges and indices compared to the polygon. Therefore the proof doesn't apply (it's not going to color the additional interior indices). The proof is still wrong, just not for your reason.
@RoderickEtheria5 жыл бұрын
4:09 2 guards would be enough there, though, as long as you removed the argument that they had to be situated at the corners, so it's a bad example. If you bent any of those middle points to not be fully visible from the outside, you would have a point though. 4:36, again only 2 guards needed here. You are only connecting the triangles of points 2 distance away, when the lines for the triangles could be placed between any 2 vertices that don't force you to draw outside the shape for them to be reached. This said, the easiest way to determine the visibility of an area is to extend all lines extending from vertices to the edge of the shape. All points found within the lines extending from a vertex can see that vertex. If there is a vertex inside these lines, extend a line from the original vertex using along which this interfering vertex would fall to the edge of the shape. This will create a number of shapes that can see certain amount of vertices. Find the point or a point that can see the greatest amount of vertices, and shade every point it can see. Then look at the remaining area and look for further overlap of vision. This does a remarkably better job than drawing those triangles.
@RoderickEtheria5 жыл бұрын
@Stratowind I extended the edges on both the right triangular extensions and you are incorrect. They cross before the edge of the figure.
@abl96435 жыл бұрын
4:09 ok but that’s a condition. There would only be one guard needed if he could see through walls but that’s not the point. 4:36 is only a demonstration of the rule he expressed, not a minimal amount of guards
@RoderickEtheria5 жыл бұрын
@@abl9643 The original question asked how many guards would be needed to see you regardless of where you were. Originally, this didn't require the guards to be standing in corners. Later on, he adds the condition that the guards would be standing in the corners. Also, we are trying to narrow the upper limit which, given the condition was not originally there but later added, should not require the guards to have to be standing in the corner.
@spanishislandsquattingduck31755 жыл бұрын
What i'm liking about these kinds of videos, is that more than just explaining the problem and going through how to solve it, they're also explaining how to use and make proofs and why they're so important.
@joschistep34422 жыл бұрын
🤔 The guards have 360° vision, but in which dimension? What if their vision is limited to a plane parallel to the ground? Assuming that the room itself has dimension 3, this would mean that we need indefinitely many guards to guard any room. Or is the room as well two-dimensional? Probably, because the proof only was about two-dimensional shapes. Do we have proof that this also applies to rooms with 3 or more dimensions? What about 42? If we have a room in dimension 42, how many guards do we need to watch it? As many as the quantity of roads a man must walk down? The answer very very likely depends on the dimension of the guards vision. Yes. I think so too.
@humantna2492 Жыл бұрын
my guess is that if you can draw a point from the center of the shape and it never leaves the bounds of the shape and then goes back into it, then it’s only 1 guard. as for anything else i have no idea
@Christian-xb8ze Жыл бұрын
Hi
@rcengineer3 жыл бұрын
Of course none of this matters because everyone who's ever played a stealth game knows that these places will have conveniently placed chandeliers and ceiling-level ducts everywhere, which the guards will never check
@dfferentpoint5 жыл бұрын
If there is less then 90 degrees a guard must be place to see it let's call 90 degrees h h < n/3 =if h n go with h
@Edgeperor4 жыл бұрын
It’s simple. You just need to make sure that your architect isn’t a complete idiot
@lacamendry1731 Жыл бұрын
3:00 Upper Limit is very easy, just need 2 guards. One at the corner of the L shape on the right, then the other guard is at the corner of the big L shape on the left. So both guards can see end to end and overlapping. I hope I explain it right.
@Katharinka0075 жыл бұрын
You + Explaining Maths = Pure Happiness ❤️
@mohamededbey5 жыл бұрын
Well done man you really do have a talent in explaining not only engineering concepts, but STEM concepts in general. Speaking of P versus NP problem I really do wish you make an entire series about it not just one video. Thanks a lot
@derre985 жыл бұрын
At 4:07 two guards would actually be enough instead of three like the video says. Like this: if instead of the two rightmost guards only one is placed approx. 3/4 of the way from the left near the bottom side. I presume based on 1:55 that the guards don't have to be placed at the main vertices. One would have to make the rectangular region of this gallery a bit shorter in vertical direction for 3 to be required. Not that this changes the message of the video in any way, but it just happens to be the geometry in that particular picture.
@zachstar5 жыл бұрын
You're right, if we assume guards must be placed on vertices then three are required. I should've extended the triangular regions cause then three guards really would've been required no matter where they could be placed.
@CheapoPremio Жыл бұрын
I know a rule is to only place guards at corners, but for the gallery at 4:00 two guards would suffice if you remove the two on the left and replace it with one at the bottom where the extended lines of the inner walls of the two triangle extrusions meet.
@maxxernB Жыл бұрын
4:07 you can watch whole area with just two guards, take away the middle and right guard and place one guard at the bottom in which he has angle for both middle and right spike areas of the room
@forcequit29284 жыл бұрын
I don't understand the logical jump at 6:08, imagine instead of just one inner vertex, there is like a "W" shape of several verticies that are "within" the original attempted triangulation. If you "slide the segment closer" and reach any particular vertex, say the middle of the "W", you are not guaranteed that that vertex will be part of a triangle with the original point.
@willwu42304 жыл бұрын
Exactly. The theorem is correct but this proof is wrong.
@undeadman76765 жыл бұрын
Everybody: awesome video! Me: big ass dominoes
@ExplosivePine4 жыл бұрын
What
@obviouslykaleb79984 жыл бұрын
Explosive Pineapple 6:20
@k3melow Жыл бұрын
The problem is having a museum in first place
@aashsyed12773 жыл бұрын
Even once I've seen your videos, these video are so relaxing that i watch them again.
@kevinfeng28763 жыл бұрын
The reminds me of the Yiga Clan Hideout in BoTW except the guards move in shapes and can be lured away with bannanas.
@stomah98323 жыл бұрын
the best way to solve a problem is to change the problem (360, only at corners, …)
@LineOfThy Жыл бұрын
Yeah try that on a test
@empurress774 жыл бұрын
For every example shown the most guards needed to observe 100% of the area is 2. You're overlooking overlap of zones of observation. In the example of the last illustration place a guard at the point at the north most R plus the point at the east most B all areas can be seen when their overlapping areas are totaled. The combination of the north most G plus the corner designated G just south of that would also combine to observe 100% of the area. Even the two R placements previously alluded to, together, would also work. I'll let you figure out what guard post would work if you have a guard at the furthest north west B point. (Hint its an R that i previously mentioned.)
@Willpower3605 жыл бұрын
Payday guards would need this
@spartanwar11855 жыл бұрын
Well, that and pray that their mission is silent only Crooks won't stop to restart if they could just blow through the rest of it
@aarongold72204 жыл бұрын
0:36 . i mean you can just use one guard. If we assume the boundries are impassable like the game, the guard would just have to stand at either the entrance or exit.
@hussam90443 жыл бұрын
that last one only needed 2 btw for whoever was wondering
@Ch1l1C0nCarnag3 Жыл бұрын
Am I the only one who noticed how the main room layout used in this example has a stupidly easy 2 guard solution that doesn't require any maths to work out given the stipulations of corners only and 360 vision? Far Right Blue, and Top Left Green. That covers the entire gallery with two guards.
@therealkrishanlal Жыл бұрын
Payday 2 has solved the Art Gallery problem
@reznovvazileski31934 жыл бұрын
Ancient Greece solved this problem long ago. They had large round and open theatres so 1 guard would've been sufficient to spot the entire thing at any time.
@qfox167895 жыл бұрын
Always look forward to a new major prep video. Keep the good work up
@mayabladewing Жыл бұрын
Love this video! The math was really interesting and I learned a lot. But, I feel like one thing that kinda frustrated me was the lack of sense. The ‘rule’ of only being able to place guards in corners held back the potential of placement a lot, and a fair few of the problems presented that required 3-4 guards only required 2 if a guard had been placed in a non-corner to observe more. That, plus the fact that the actual distance of how far you could observe a would-be intruder doesn’t make sense. Museum hallways and rooms are usually of a size that allow you to see a human figure at the end of it unless it would be a more absurd size, which most of the examples didn’t have. Still an absolutely amazing math video but if it were to be applied in an actual scenario or be attempted to be solved with just common sense it would kinda fall off.
@Mr.mustard. Жыл бұрын
For the first one can't you put 2 guards for th whole thing in the top left part of the extra area and one the very most bottom right
@catboy6451 Жыл бұрын
No matter how many guards you add, the Payday gang will find a way
@TibbelsNBits2 жыл бұрын
Already liked this channel, but the fact that you love ocarina of time just made me a fan forever
@s3ven_six3223 жыл бұрын
If the rules were different (guards weren't restricted to vertices), 4:08, 4:20, would each only need 2 guards as well... Actually, because of the angles, 2 is sufficient in one case even assuming all the rules are kept. In 4:20, place guard 1 at the topmost vertex, and place guard 2 one vertex down from guard 1. However, 4:08 doesn't work with the rules. If you could place 2 guards anywhere however, it would work. Place guard 1 on the bottom line at the point where the right triangle hypotenuse is extended to, and place guard 2 anywhere to the left where the entire far left triangle can be seen
@wr444 жыл бұрын
At 4:09, why are 3 guards needed? Keep the guy on the top left where he is, but instead of having the remaining 2 guards have one guard on the bottom line, directly below the mid-point of the top right horizontal line. That new guard would be able to see into both the middle and right triangular peaks (as well as the entire rectangular body) and that top left guard could see the remaining top left triangle.
@TheAntiBarrel Жыл бұрын
after 10 minutes I have realized this is NOT a Payday video
@CaiusNotPlaying Жыл бұрын
Going from watching your second channel to watching this is a sharp transition.
@aaronbredon2948 Жыл бұрын
For n=3x, n=3x+1 and n=3x+2, it is possible to create a sawtooth pattern that requires x guards Since n/3 rounded down equals x, for every number of sides in a polygon, there is at least 1 such polygon that requires n/3 rounded down guards.
@xcy73 жыл бұрын
Regarding the induction proof of the polygons; wouldn't it be easier to start with a triangle and connect a 4th vertex to two vertices of the already existing triangle? This easily proves any shape can be triangulated. It also proves the coloring as the 2 vertices you connect the new vertex to can only use 2 different colors, so you the new vertex will just be the 3rd color. I also feel like this resonates better with the classic m+1 idea of induction. I suppose that is kind of what you did, but backwards.
@Happyduderawr2 жыл бұрын
You can use smoothed analysis to come up with a fixed parameter tractable algorithm where the fixed parameter is the number of reflex vertices.
@BigFry9591 Жыл бұрын
That whole vertex thing was introduced way too late. All the examples given previously with the different shapes had the guard in the middle, and no vertices were ever mentioned. Then all of a sudden, it matters that guards are placed on vertices.
@tylerbakeman Жыл бұрын
This is pretty close to a BSP. Not really an important problem to solve- because BSPs aren’t used in games anymore (they have to be regenerated frequently- so they don’t do well for dynamically changing spaces), and they don’t do well with curves (memory intense). It’s more common to see Z-buffers because assets vary in size greatly (and there are other forms of culling polygons nowadays- look at nanite for example).
@ElodieHiras5 жыл бұрын
And if I had the stipulation that each guard must be in sight of at least 2 other guards at all times to make it harder to just shoot the guards with a silenced pistol?
@arnerademacker85485 жыл бұрын
You can hear change dropping in a museum, I'm pretty sure a silenced pistol is louder than that.
@Patapom33 жыл бұрын
I still don't understand why putting guards on the blue vertices is enough to cover the entire shape? Why the fact that a polygon is 3-colorable has to do with the number of guards to use???
@grimmsoul3096 Жыл бұрын
0:42 it doesn't have to work like that, you could just go the simple route of making sure a guard is has constant eyes on every way in and every way out, thus making eyes in the middle unessesary 1:23 you mean "simple" as simple does not equal easy
@Elnotronic Жыл бұрын
Gta taught me that you need more guards
@chaincat33 Жыл бұрын
wait, where is the rule that you have to use a vertex to place a guard? In the comb shape you showed you can easily see the entire thing with 2 guards if you extrapolate the diagonal line on the right tooth down to the other line and place a guard there. He can see the center and right tooth and you just need a second guard to see the left tooth
@ibemper18504 жыл бұрын
4:04 2 gaurds required, he was wrong, place one at the center of the two right tringles at the x axis and at the bottom in the y axis now place one at the bottom left most corner, this covers 3 triangles.
@GodGurdjieff Жыл бұрын
The figure you showed rgb triangles actually needs just 2 guards for whole security
@alex_zetsu5 жыл бұрын
is it still NP if you remove the vertex requirement?
@ampstamp Жыл бұрын
Tell me why I thought this was gonna be about art gallery from payday 2
@KillerKatz128 ай бұрын
No way I've seen engineer/STEM Zach before Zach star himself? And I never noticed?!
@redtheyiffer5 жыл бұрын
Payday 2 has a good example of this problem
@JustinnP231 Жыл бұрын
we need to cut these video game guards some slack, having a third person perspective seperate from your physical presence is an insane sneaking advantage
@jogugaga7121 Жыл бұрын
My dumb ass thought this was a payday 2 video.
@OrenLikes2 жыл бұрын
Nice, but was looking for guard placement ANYWHERE - not limited to vertices or edges. Thank you!
@charger8624 Жыл бұрын
I can’t look at this without thinking of payday. Thanks youtube recommendations!
@naverilllang Жыл бұрын
Great video. Unfortunately you didn't account for polygons with a turning radius greater (or less than) 1. For example, a pentagram would need a whopping 6 guards, despite having only 5 vertices. I think that the proof should state that it only applies to polygons with a turning radius of 1, although a generalization for polygons with any turning radius would be fascinating.
@Kallermatsch37 Жыл бұрын
I don't really understand why this problem exists. It's easy to solve for any human and AI's could probably brute force the optimal solution in milliseconds. Maybe I'm missing the point here but I feel like this video does a poor job of explaining why this whole problem exists in the first place.
@danielrhouck4 жыл бұрын
What about smoothly curving art galleries; is there anything that can be said about those? (If the curves don’t need to be smooth you can get fractals, which can need infinite guards)
@dAni-ik1hv Жыл бұрын
i just realized that Zach looks super happy and excited during his vids but he also looks like he hasn't slept in 3 days