I am currently working on some computational geometry problems with non-euclidean metrics, and have some trouble on a fact that sounds easy enough, at least intuitively.

The fact is as follows:

Given a line segment and two points p,q in the plane, which conditions need to hold such that the point on the segment that is closest to p,q (i.e., sum of the distances to p and q) is one of the extreme points of the segment?

This is easy enough if the metric is l1 (Manhattan) and the segment is horizontal (or vertical). In this case, it is sufficient that at least one among p and q is outside the vertical "stripe" defined by the extreme points of the segment.

The metrics I am most interested in are fixed orientation metrics. I guess that something similar to what happens for l1 would be true also for fixed-orientations, but I am not sure where to start for proving it.

I am reading through the papers of Widmayer, Sarrafzadeh, and others trying to get the hang of it. I was hoping some of you could refer me to other readings.

This is probably not the right place to ask, since it is more related to topology rather than computer science. However, being a computer scientist myself, I would find it more comfortable to read something written by a computer scientist.

Thanks for your help!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.