Mod-05 Lec-11 Intersection of Half Planes and Duality

Welcome to lecture eleven of computational geometry. So, we will start only new problem which is actually related to the problem of convex hull and I will establish that relation in the course of lecture, but let me first state the problem Ah. So, we are what we are given. So, we can talking about a this problem is intersection of half-planes. So, we are given a set of half-planes what is a half-plane look like is basically bounded by a line bounded by a line and you know 1 side to the line is the half-plane that we have we know will be pertaining too. So, you know I will just shared this indicating that you know this is the side of the half-plane that I am interested in That’s half-plane I am talking about the line divides the plane into 2 half-planes So, the shaded side is the one that I am pertaining to. So, this is 1 half-plane you know that is another half-plane lets called this H 1 H 2 you know and have more half-planes H 3 H 4 something H 5 and. So, on. So, forth So, given these half-planes by the way half-plane is a a very simple example of a convex set right half-plane is convex and you can prove it by definition convex the entire segment of the 2. lying inside the half-plane will also be inside the half-plane Right. So, half-planes is a convex set and what I am interested in is given a set of let us say n half- planes set S of n half–planes compute the intersection. So, H I 1 to n which basically means the region common to all half-planes now in the example that have given here I mean just the infection what does it look I mean should be common this this region should be common to all half-planes. So, for instance a a is this point common to all half-planes Now, because this point certainly does not satisfy h 5 right is this point common to all half-planes Now, because it certainly does not satisfy h 4 right h 4 is h 4 is this this thing and the point is to the other side of h 4 Does this satisfy all constrain all all half-planes there is region common to all half-planes Yes ok. So, if finds this 1 is common. So, what we are interested in is not just 1 or 2 points, but they entire region that is common to all the half-planes and because half-planes are convex by definition the intersection of half-planes will also necessarily be half-plane And what is the intersection of all half-planes and what kind of region is that it is a convex region and it may be a convex it basically a convex polygon right It is a region which is convex and is bounded by straight lines which are essentially the lines bounding the half-planes. So, intersection of half-planes is a convex polygon provided Well I am not even talk about n 1 n 1 is 1 situation yeah sure it is not a strictly speaking if the convex polygon yeah the polygon is essentially bounded this may not be bounded

that is one one problem What is the other problem Intersection can be null exactly the intersection may be empty right. So, so the common region is convex polygon in most cases, but caveats is may be unbounded and other problem is may be empty Fine how do we deal with a unbounded is a a simple way of dealing with unbounded. So, you do not have to construct a consider this as a special case when we are trying to design a algorithm Yeah we are saying that I put a kind of a window Right and the window should be a rectangular window let us say we should be large enough to contain Right see good. So, that is I was say So, since it is unbounded of course, the the rectangle region I am to be. So, the rectangular region suppose is some rectangular region what I what want is that want make make sure that even if it is unbounded Also this is not unbounded . So, this region looks like unbounded right. So, these 2 edges do not into converge what you know basically they they going to go. So, I can clip it using this rectangular window and I will be happy to set of and and it kind of it contains all the vertices of the of the of the intersection region right. So, this misses out of on the unbounded thing, but a as long it it has it has adequate description of this this intersection region because it it captures all the vertices and all the vertices corner points essentially going to be corner points of the they they will be described by 2 or more let us say lines bounding the half-spaces And therefore, you know you can actually in some sense compute somehow these smallest a if you compute the smallest and the largest ah intersection points you know both in x and y deduction that could be one that could find this rectangle because there we no vertices falling outside the rectangles So, that is one way to sort of deal with this this kind of situation where it is unbounded we now the question of poses how do you compute this smallest and largest you know let me not get into that part what just just. So, that you know we we can a we can we do not have to deal with unbounded regions is what I am saying. So, some way we can simplify the whole thing without having to talk about unbounded regions essentially all I am saying is that we have some extra kind of half-planes defined by these lines. So, along with the given half-planes I am also looking at essentially these 4 half-planes And then that will bound the entire intersection So, the entire intersection is become bound, but emptiness is something that we cannot push it away why. In fact, emptiness is a very important problem. So, so 1 motivating problem for this finding in intersection is a can you tell me give me 1 example of why are you interested in intersection of half-planes exactly. So, a basically the constraints a linear constraints are basically half-planes right. So, ah 1 of an and it is an known that

the problem of finding weather there is a feasible solution and the problem of actually solving the linear program they not be very different in in complexity So the problem of finding intersection is almost equivalent to finding actually the optimum point So, So, just to find out if a given set of half-planes has a non non-prevail intersection that is the it is not empty that itself is is is a is a basic fundamental problem and you cannot push it away So, given a set of half-planes just the problem tell us whether I mean to to determine whether or not it defines a feasible there is non-feasible region is a basic problem. So, I cannot push that away right So, whenever. So, in to solve this problem find in the intersection half-spaces I have to deal with this 1 possibility that the intersection can be empty and we would not know in advance intersection is empty that will discover over the course of the algorithm algorithm should be able to tell us whether or not it is a intersection. So, you can see actually this problem you know simply stated in 2 dimensions you know as you move to higher dimensions and it could become quite complicated. In fact, the linear programming is nothing, but the the constraints in a linear constraints in arbitrary direction arbitrary dimensions So, you have these half-planes which are constraints in d dimensions and then there is some kind update functions and that is you know. So, fiinding the finding 1 point if the feasible region that we finding the optimal point in the feasible region and I am saying I am claiming right now is the not very different in complexities if you can find 1 you can find the another, but you know this problem that we discuss in today I will be discussing independent of polymer linear programming, but they this certainly you know some relevance to linear programming except that in linear programming we do not have to find the entire region So, actually linear program into some ex10d you can you you may think about perhaps it is simpler than this problem because I will be happy to find only 1 feasible solution which is optimal solution I do not necessarily have to find the description of the entire feasible region which is which could be a convex polygon in 2 dimensions or a convex poly tope in high dimensions although the we have not discuss this issue before this, but let me just a mention that the convex all in higher dimension which is that intersection of n half-spaces in in dimension d what is the kind of descriptive complexity it may have I mean that that that structure you know how complicate that we in 2 dimension it is a convex polygon. So, that description that structure is defined by let us say n corner points or the n adjacent So, forth in 3 dimensions may have already brought it of once right. So, that that the description is very similar to a In 3 dimensions if I take the intersect of n half-planes in 3 dimensions and suppose that intersection is non empty that region is a convex 3 dimensional convex poly tope and what is the how did you describe in 3 dimension convex polygon How many phases how many corners and how many edges yeah, but what is the total you know description and what what is the complexity of that that structure no no what is 4, but vertices for 4 triangles no no no no you are talking about tetra hydrons am not talking about tetra hydrons intersection of 4 half half half spaces in 3 dimensions I am I am I am mentioning a given n half-spaces in that is in 3 dimensions the intersection is suppose is non-empty it is a convex 3 dimensional convex poly tope what is the how do describe the what is the complexity of the structure in how many phases how many edges how many corners n c 2 n c 2 will be already n square kind of complexity right exactly. So, essentially the 3 dimensional convex poly tope you know is is nothing, but the plane a graph which for. So, that is you know you can euler’s formula follows that you know that you know a a a 3 dimensional structure Ah a plane. So, because this all convex need not only the whole thing is convex the whole intersection is convex if I if I limit if you limit yourself a plane look at 1 of the planes and look at the projection just look at the intersection of the remaining half-planes with this planes

Suppose I take the intersection I restrict myself to 2 dimensional plane 1 of the phases right. So, this is the 3 dimensional structure Let let us say I take 1 phase and I only look at the the the structure of 1 phase that is that is a 2 dimensional structure. So, that itself again will be a will be convex right so. So, now, from here it kind of follows that you are not going to have you know a the plane can only describe at most 1 phase you cannot have the same plane describe to 2 disconnected phases because that would not be convex So, therefore, it follows that the number of phases of this intersection is bounded by the number of number of planes yeah n right So, so there no more than n phases in the of the 3 dimensional structure and in the n phases by euler’s formula and a plane a planarity for the what were the plane and graph formula it follows the number of phases and number of vertices and a number of edges in a graph there are kind of linearly related ok So, the entire structure this 3 dimensional convex poly tope described by the intersection of n half-planes still has a linear structure it is it is it is not n choose to vertices I can say that right So, So so in 3 dimensions as a 2 dimensions you still have a linear structure in 2 dimensions very simple it is exactly an in 3 dimensions it is a planer graph kind of structures. So, it is a order of an, but there after you know things become moiety So, you a when you wants to go to 4 dimensions you cannot visualize the first you have to resolve other ways of you know figuring out what the what the complexity is and without getting into too much details let me say that the complexity grows roughly has n to the power of d over 2 So, it is like in. So, higher dimensional convex poly tope defined by intersection of n half-spaces that grows as roughly n to the power d over 2. In fact, there is a kind of flow on that right And this is known to be theta. So, there are actually convex poly topes which can have that many number of its it is not the phases its its everything its dimension 0 is vertices is dimension 1 that edges. So, all the facets of dimension 0 to dimension d minus 1 So, that can grow exponentially essentially So right So, if d is 2 or 3 you can see this is essentially order n then moment d becomes 4 it becomes n square and there after it really it really becomes the you know quit heavy And therefore, we actually solve linear programming you are not going to compute this entire feasible region because of feasible can be can have an exponential size and no way you can actually if you if you want to do it in polynomial time you cannot the 4 to compute this So, I am just trying to draw a line between that the fact that I am we are not really trying to attack the linear programming by constructing the intersection although intersection contains a all the information about linear programming, but you know we cannot construct it But of course, in lower dimension like we are dealing within 2 dimensions 3 dimensions we can we are just looking up on as it as a problem which is interesting you know other applications also And this has and the and the size is at most order n intersection. So, one thing let me do again ah like we did for this a convex hulls. So, this seems to be at least intuitively some sort of connection between convex hulls and an computing the intersection of half-spaces in the sense that both of them eventually give us some kind of convex polygons right But what is real relation of why should you know something that is discribed by points related to something will displayed in a half-way in when we we cannot we cannot appreciate that right now, but we did one thing when we try to compute the convex hull you know at least in in terms of conceptual simplicity we were able to dealing the upper hull over n 10 we we growly describe the algorithm in

terms of upper hull or lower hull right So, here I will take a similar root where I do the poly I will distinguish between half-planes that are downward pointing I will just say what I mean by downward pointing and upward pointing of course, I miss not something something which can either downward or not nor upward any way first let us say what were downward point is if this half-plane we have a half-plane say essentially now it is this what I am saying downward pointing and this is a half-plane that I am saying is a upward pointing One quick test for this is the half-plane is going to be describe some kind of inequality a linear inequality a quick test could be does this contain a the point you know y is equal to minus infinity a something This is essentially contains y equal to plus infinity. So, just see that whether or not this satisfies the inequality. So, I am I am just dividing the set of given half-planes into these 2 of course, there this kind of thing which is neither upwards or downwards since I cannot handle this you know we will say that these do not happen And why can why cannot this happen will just do a know random notation good. So, you are; obviously, the same language you know. So, these kind of bad things do not happened to us right right. So, now, now I am just coming to that I am just coming to that. So, now, once I have I have I have separated them out these 2 kinds of things Then we talk about essentially a the intersection of downward half-planes and intersection of upward half-planes right. So, we compute them separately which means that the downward the first case you know you can imagine that all contain minus infinity y equal to minus infinity So, it will looks like something like this and clearly if there is there are any of these downward half-planes the intersection is non empty portion Because all them will contain that minus infinity point. So, in somewhere we have also done away with this emptyness problem by separating half-planes and the upward ones we look like you know something like you know again this will be non empty and after we have computed them what do you do because we have to find out the intersection a yeah you know you know it is not pasting it is not pasting let me point out this is not going to be pasting into simple pasting It it could be more complicated than that, but eventually for the final answer will have to compute you know this intersection point and whatever is the intersection point and by the way this could actually be more complicated like this this could go on like this this and. So, on so, but finally, you know this is the region that we are interested in after you compute the intersection the downward half-planes after we compute the half-planes will again have to deal with finding the intersection of these 2 objects, but then you can see after all these objects has nice structure you know these are both kind of chains these are you know one one as you know this this kind of a structure is usually called convex chain right The red one is a convex chain red block one is a kind of convex chain there also monotone ok So, we are too nice you know monotone chains and therefore, claim that intersecting these will be fairly easy and this is also a problem for in one of the these one of the assignment problem where a in generally your asked to find out the intersection of 2 convex polygons So, this can be dealt with in that frame work

also this is this kind of viewed as the problem of finding intersection of 2 convex polygons and whatever time it takes the suppose you know it takes order n time its order n times it is a log n time it is log n time So, finally, let us let we let we just say that it can certainly in order n time that is for you figure out how to do it exactly and. So, will not bother about this final step of you know how do you find intersection of the convex and the concave chains or the regions regions actually Ah chains sorry upward region and the downward region. So, will now focus on just one of them let us say intersection of downward half-planes now I could try to not describe or define or develop an algorithm from scratch which at this point you know I would not attempt to do not now I will to just find out or explore does this have any kind of relation with what we have done just before this that is that the convex hull computationok Now; obviously, these are too looks like very 2 different 2 very different problems you know in 1 case dealing with points when we are talking about convex hulls So, convex hulls has point input and intersection problem has half-plane input which can also we thought of thought with the sort with the half-planes are actually described by lines let us say It is 1 side of the boundary line right in 1 case it is a point input that other case kind of a line input. So, somehow we need to be able to do some kind of correspondence between lines and points to be able to to to able to find out if there is any relation between these 2 structures at all All right. So, for that we will will resort to what is called some kind of duality relation some duality function let us say a duality map into more precise So this duality mapping let me define as d of a. So, what this duality mapping will do for us it will map points 2 lines and vice versa what is a point a point is a usually defined by a coordinates right. So, point So, we are this we are dealing with 2 spaces right the space of points as space of lines So, to be able to define a kind of mapping So, what do you mean by point to point is a order pair of coordinates a b whats a line a line has basically a parameter equation right So, a x plus b y plus c is an one possibility, but then a there is because I want to let it to the points. So, actually the line is a 2 dimensional structures again you should have only 2 parameters. So, if you think about the y is equal to m x plus c this is basically parameterized by the slope on the intersection my space of points of course, is a obvious choice of pair order pair of coordinates and for the lines we again choose the. So, now, we are choose the m comma c representation So, that we are dealing with 2 dimensional phases. So, in both phases. So, it is a mapping from 2 dimensional phases to 2 dimensional phases right So, this is what this duality mapping will do for us now in literature there are lots of ah you know different kinds of duality mapping and they have different kinds of properties So, I will first try to describe what are the preferred properties for the kind for the duality function that we used and then later instantiate one’s specific function that achieves all these properties So, let me first try to elaborate an what kind of properties you know this mapping should

satisfy what that if if you satisfies then we are in good share So, one thing that will do first is is say that itself inverse. So, desirable properties I will say. So, d of d’s of x equal to x x is either a point or line they want it to be self inverse ah So, if I apply the dual transform if x is a point apply the dual transform get a line and if I apply the dual transform for this line we get the point vice versa If I x is a line apply a dual transform line I get a point and again apply the dual transform I get back the same line So, this is 1 property would like to have another property is that you know is a is let us say 1 is to 1 most good mappings would have this properties I mean useful mappings have this properties. So, I want to trying to list the desirable properties I have not even said what function actually will actually satisfies the properties ok Now, here is a very important thing till now you know these all fine incidence. So, incidence properties is a following consider a point p and a line l incidence property says that if p is incident on l then d is of l which is a point is incident on d’s of p is a line. So, its incidence preserving the mapping that we are in interested in we will be incidence preserving if a point happens to be an a line and I take the dual transform of the point then it is a line a dual transform is a point and again that point should be incident of a line. So, whatever function you interested in should satisfy this property This kind of implies a following if l 1. So, l’s will be like line l 1 and l 2 intersect in p. So, p is a points l’s of lines in p is a points ok If 2 lines l 1 and l 2 intersect in p right l 1 l 2 p then d’s of p which is the line can you completed yeah should pass through d’s of l 1 and d’s of l 2. So, does is follow from 3 follows some 3 because the incident property if it incidence a is preserved then this point should lie on both lines and therefore, this line should pass through both these points So, it is a consequent of 3 it is not a separate property, but just to highlight something that you know will be able to use make use of this property When we talk about this connection between l’s n intersection of half-spaces right So, so one more thing. So, we are talking about incidence of what is the point does not lie on the line So, it is either below or above. So, we need to say something about again the orientation So, above sorry above or below property So, say that if p lies above l now the above I thing the same way that we talking previously

that you know plus. So So, here is a line So, it is a line l and p basically is above l just what do you mean by p above right So, p lies above l then d’s of l which is a point l ok is exactly on what kind of function finally, choose so, but I will just prefer this 1. So, above below. So, if a point is a above l d l d’s d’s of l will be below d’s of p You just interchanging the orientation, but its consis10t suppose all points and lines this will represent. So, again let me not even get into what function we satisfy all these properties I just use the properties to establish suppose such a function exist such a duality mapping exists then will try to use this to show the connection between hulls and intersections So, again we have limiting our hulls to when we talk about intersection we only talking about this you know downward planes or upward planes. So, here is basically what we are try to establish So, given set of downward half-planes let I of h denote intersection now consider the duals of the lines describing the half-planes h and denote it by S right. So, we have given a set of h downward half –planes the half-planes are described essentially by s Bounding line and which side of the line it is we know that it is a downward side that will obtain now we consider the duals of the bounding lines that describe the half-planes that duality is defined right where this a line to point duality that those points I am calling it S let c h of S is denote the convex hull of S So, just to draw the distinction we have this is my downward intersection of downward half-planes right now I am talking about convex hulls of points which are the duals of those lines described in the half–planes and here is my convex hull or the duals of the of those

lines the points of the duals of the lines So, what relation thus these blue structure have this structure will does not look like mind that blue structure looks about half that of the rate structure In fact, is half that of the rate structure So, what will establish is that you look at the chain which is that the the lower hull consider only the lower hull. So, lower hull is this structure if this again some kind of convex chain upward convex chain So, blue one is downward convex chain the black one is the upward convex chain which is the lower hull of this set of points right and now the claim is that at this is 1 to 1 correspondence between this lower hull and that blue structure Right namely that the half-planes that describe the boundary the half-plans that describe the boundary or in 1 to 1 correspondence with the points that describe the lower hull. So, this is the The yeah Exactly. So, the downward convex chain describing the intersection of half-planes is in 1 to 1 correspondence with the points which are duals of the lines describing h this is the lower hull Namely suppose I am just saying suppose this is half-plane half-plane 3 and half-plane 2 and half-plane 10 and half-plane 20 and half-plane you know 50 and somewhere that these points would correspond to the dual So, this point will be dual of the half-plane the line describing the plane 3 So, like dual of 3 this is dual of 2 and dual of 10 and. So, on. So, forth dual of 50 suppose this is true before even a we have approved it suppose this is true then how will you construct the intersection of half-planes you just take the then you will go the dual space basically you know even half-planes Look at the lines described in the half-planes look at the duals of those lines which are points use your favorite convex hull algorithm to construct the convex hull of these in the dual space which is which is the set of points and then the lower hull of that is in 1 to 1 correspondence with the intersection. So, once I know this is you know these are the these are the 3 d’s of 3 d’s of 2 are the points then I immediately get the I can from there I can simply get this structure that this convex chain is the intersection has first it first start with 3 then then then the boundary is defined whether the half-plane 2 with the boundary is defined with the half-plane 10 and. So,on. So, forth So, we recover the structure right away from there if this this claim is true why is this came true let me switch to the we will; obviously, try to use the the properties that we claim you know some there is some mapping that will have this properties and and that is the kind

of dual duality transform that we have using So, these are all downward this is my intersections this particular half-planes maybe I should actually draw them in red. So, this half-plane is even not even part of that boundary this So, the the intersection the the description of this intersection you know is essentially the the chain the chain of the half-planes that describe the boundary of the intersection if that is what we that is what we are interested in. So, the red some like this these half-planes do not even figure in the intersection. So, the description of the intersection does not even contain these half-planes So, those are basically I am saying like you know some points are going to be on the hulls some points are not on the hull this is equivalent of the corner vertices We now we have a what is the property of this boundary this boundary. So, why do thing that you know this half-plane in is part of the boundary where as you know the red is not you know some something something that is here Is not no no lets talk to the dual we are just trying to characterize this only in terms right in other wards you can think about it like this you know if you looking at you know suppose I am trying to draw plot a function which is let us say at any point x what is the minimum what is the minimum y that we are looking at. So, suppose these are functions these these these these half-planes like are functions you know these are linear functions any point of time I am looking at the min of the the the lines I mean which is ar the lowest. So, if you draw a lines these are the intersections. So, this is the lowest So, that is why it is part of the intersection a a half-plane. So, of course, this this this you know you move this x to here and it still you know this function is the lowest, but some point a next intersection points it changes next this function becomes a lowest. So, it is it something what is called a lower profile It may not does not even to be linear functions you can describe you you can define in terms of any kind of function I can have any any arbitrary function ok and I can look cause the and define the lower profile in the same way that any point point wise minimum among all the functions is the overall lower profile is what we calling So, this is one way to characterize that you know something will become a part of the intersection something some half-plane will not be a part of intersection so now we are going to now now let us go to the dual space I mean are are you happy with this characterization then only basically So, some half–plane will be a part of the output only when it becomes a minimum for some x So, now, when you go to the dual space where you know this line becomes a point all all all lines bascally some points When is a point a. So, so given a convex a set of points. So, a point is a part of the a you know a you know a final description of the convex hull or a corner point if we can draw a half-plane or a line through this point a tangent namely say this is size is point you can draw tangent through the point such that all other points are above this line right Can you do now can you see the correspondence between the a dual transfer preserve well

preserved means is that just switches the upper and the lower thing ok So, I am able to draw a line through the point now use the the incidence property the dual transform of these point this point Is one of these lines that that is how I got these points from right this line is some arbitrary line that passes through the point So, a dual of this line dual of this line will be some point will be some point on this line right. So, this one will become some point in the line may be it is a d of t. So, there is a point basically where all other points lie above this above this tangent and at the same d’s d’s of t point they satisfies it satisfies all the half-planes it is below of the half-planes that is all that is the proof no I its above below right. So, these points are above and this point is below all the all the lines its we are switch the upper and a above the line and below the this things if the if the point is above the line the dual of the line will be below the points So, just switched that is why we are looking the lower hull and the and the downward chain So, I will stop here today You know is need meditate a little about it this, but tomorrow hopefully and you know in the next class will be continue about this