I take it from the problem description that you are given n intervals [r1(i),r2(i)]_i=1^n and are to choose an x(i) in each interval so as to minimize the maximum value of |x(i)-x(j)|. The intervals may overlap, in which case you may be able to pick equally-spaced points, or they may not overlap, in which the endpoints of the intervals become constraints on the selection of the x(i), and may prevent you from selecting equally-spaced points.
Dave On Oct 21, 10:21 am, Vivek S <s.vivek.ra...@gmail.com> wrote: > to maximize the minimum distance between any two points:-> to maximize the > minimum distance between adjacent points > -> for this all points must be equally spaced. > > hence, choose 'n' equally spaced points in the range (r1, r2) starting from > r1 and ending at r2. > > 2009/10/21 saltycookie <saltycoo...@gmail.com> > > > > > > > Yes, you are quite right. If I am not mistaken, you give a good solution > > for finding the minimum maximum distance. > > > But what about the original problem where we want to find the maximum > > minimum distance? I am not clear about the connection between the two > > problems. > > > Thanks. > > > 2009/10/21 Dave <dave_and_da...@juno.com> > > >> 林夏祥 , think again. If we are trying to minimize the maximum distance, > >> then we want to minimize the upper bound. That is what I specified: > >> letting c be the upper bound, find the smallest c such that all of the > >> distances do not exceed c. That gives rise to the inequalities > >> |x(i)-x(j)| <= c. > >> If necessary, this can be written as two inequalities: > >> x(i) - x(j) <= c and > >> x(j) - x(i) <= c. > > >> Since the relationship is "and," we can just use the two inequalities > >> as part of the constraint conditions. > > >> Dave > > >> On Oct 21, 12:02 am, 林夏祥 <saltycoo...@gmail.com> wrote: > >> > I don't think LP can solve it. We are to maximize c, not minimize c. > >> > The formulas we have are: > > >> > |x(i)-x(j)| >= c for all i and j > >> > r1(i) <= x(i) <= r2(i) for all i > >> > The first inequality actually is combination of two linear equalities: > >> x(i) > >> > - x(j) >= c or x(i) - x(j) <= -c. Notice the relation of the two is > >> "or", > >> > and we cannot put them together to get a system of linear inequalities. > >> > 2009/10/21 Dave <dave_and_da...@juno.com> > > >> > > This is a linear programming problem. The way you formulate the > >> > > problem depends on the capabilities of the linear programming software > >> > > you have. > > >> > > Basically, you want to > >> > > minimize c > >> > > by finding x(1) to x(n) such that > > >> > > |x(i)-x(j)| <= c for all i and j > >> > > r1(i) <= x(i) <= r2(i) for all i > > >> > > Dave > > >> > > On Oct 5, 9:22 am, monty 1987 <1986mo...@gmail.com> wrote: > >> > > > We have to locate n points on the x-axis > >> > > > For each point xi > >> > > > the x co-ordinate of it lies between a > >> range > >> > > > [r1i,r2i] > >> > > > Now we have to decide the location of points such that > >> > > > minimum { distance between any two points } is maximum. > > >> > > > Any answer is welcomed. > > >> > -- > >> > 此致 > >> > 敬礼! > > >> > 林夏祥- Hide quoted text - > > >> > - Show quoted text - > > > -- > > 此致 > > 敬礼! > > > 林夏祥 > > -- > "Reduce, Reuse and Recycle" > Regards, > Vivek.S- Hide quoted text - > > - Show quoted text - --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---