1
\$\begingroup\$

Given n points, choose a point in the given list such that the sum of distances to this point is minimum ,compared to all others.

Distance is measured in the following manner.

For a point (x,y) all 8 adjacent points have distance 1.

(x+1,y)(x+1,y+1),(x+1,y-1),(x,y+1),(x,y-1),(x-1,y)(x-1,y+1),(x-1,y-1)

EDIT

More clearer explanation.

A function foo is defined as

foo(point_a,point_b) = max(abs(point_a.x - point_b.x),abs(point_a.y - point_b.y))

Find a point x such that sum([foo(x,y) for y in list_of_points]) is minimum.

Example

Input:

0 1
2 5
3 1
4 0

Output

3 1

Eg: Distance between (4,5) and 6,7) is 2.

This can be done in O(n^2) time, by checking the sum of each pair. Is there any better algorithm to do it?

\$\endgroup\$
11
  • \$\begingroup\$ I don't understand how the diagonal distances are the same as the perpendicular distances. Also, I'm not sure I understand: are you you asking for the average of the n points? \$\endgroup\$ – Griffin Aug 14 '11 at 20:12
  • \$\begingroup\$ Edited the question \$\endgroup\$ – Greyhound Aug 14 '11 at 20:20
  • 1
    \$\begingroup\$ This isn't really a puzzle - wouldn't it belong to SO? \$\endgroup\$ – user unknown Aug 15 '11 at 4:03
  • 1
    \$\begingroup\$ Crossposting: stackoverflow.com/q/7059500/312172 (with python-tag, there) \$\endgroup\$ – user unknown Aug 15 '11 at 4:06
  • 1
    \$\begingroup\$ @user unknown: How do you define "puzzle"? For me, the puzzle is finding the more efficient algorithm, and I'm having fun working it out. \$\endgroup\$ – Joey Adams Aug 15 '11 at 10:11
2
\$\begingroup\$

I can imagine a scheme better than O(n^2), at least in the common case.

Build a quadtree out of your input points. For each node in the tree, compute the number and average position of the points within that node. Then for each point, you can use the quadtree to compute its distance to all other points in less than O(n) time. If you're computing the distance from a point p to a distant quadtree node v, and v doesn't overlap the 45 degree diagonals from p, then the total distance from p to all the points in v is easy to compute (for v which are more horizontally than vertically separated from p, it is just v.num_points * |p.x - v.average.x|, and similarly using y coordinates if v is predominately vertically seperated). If v overlaps one of the 45 degree diagonals, recurse on its components.

That should beat O(n^2), at least when you can find a balanced quadtree to represent your points.

\$\endgroup\$
1
  • \$\begingroup\$ nice. this should be on the stackoverflow page. \$\endgroup\$ – Neil G Aug 17 '11 at 20:41
1
\$\begingroup\$

Python

def median(lst):
    """ sort of median of a list """
    return sorted(lst)[len(lst) / 2]

def median_point(points):
    xs = [point[0] for point in points]
    ys = [point[1] for point in points]
    return (median(xs), median(ys))

points = [
    (0, 1),
    (2, 5),
    (3, 1),
    (4, 0),
]

print median_point(points) # (3, 1)

It calculates the median of the x and y coordinates separately. I'm not positive that that's correct in all cases, but it kind of seems like it might be. It's O(n log n).

\$\endgroup\$
2
  • \$\begingroup\$ Calculating the medians separately means you may get a result that isn't one of the original points. In your example, if you replace (3,1) and (4,0) with (3,0) and (4,1), it will still print out (3,1). \$\endgroup\$ – migimaru Aug 17 '11 at 23:38
  • \$\begingroup\$ Ah yes, I didn't notice that was a requirement. \$\endgroup\$ – recursive Aug 18 '11 at 1:45
0
\$\begingroup\$

Scala

object Median extends App
{
    var(xMin,yMin,xMax,yMax,a,x)=(100000000,100000000,-100000000,-100000000,"",Array.fill(2)(""))
    var points=Array((100000000,100000000))
    a=readLine
    while(a!=null)
    {
        x=a.split(" ")
        if(x(0).toInt<xMin)xMin=x(0).toInt
        if(x(1).toInt<yMin)yMin=x(1).toInt
        if(x(0).toInt>xMax)xMax=x(0).toInt
        if(x(1).toInt>yMax)yMax=x(1).toInt
        points=points:+((x(0).toInt,x(1).toInt))
        a=readLine
    }
    var middlex=(xMax-xMin)/2
    var middley=(yMax-yMin)/2

    var meanPoint=(100000000,100000000)
    var shortestDistance=100000000

    points.map(x=>
        {
            var s=(math.abs(x._1-middlex).max(math.abs(x._2-middley)))
            if(s<shortestDistance)
            {
                shortestDistance=s
                meanPoint=x
            }
        })

    println(meanPoint)
}

Takes in the points, keeping track of the highest and lowest values of x and y.
Uses those values to find the midpoint of the square defined by xMin,yMin,xMax,yMax.
Finds the point with the shortest distance to that midpoint.

Never was very good with that Big O business, so I couldn't tell you what it is for this algorithm.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I don't think that will give you the correct answer, especially if the points are clustered. For example, if the points are (0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2) (10,10), the correct answer should be (1,1) - total distance of 17. Yours would return (2,2) - total distance of 21. \$\endgroup\$ – migimaru Aug 15 '11 at 0:03
  • \$\begingroup\$ @migimaru Hmmm...I'll have to rethink. \$\endgroup\$ – Gareth Aug 15 '11 at 7:05
0
\$\begingroup\$

Haskell, 136 characters

main=interact$show.n.q.map read.words
n x=snd$minimum$map(\p@(a,b)->(sum$map(\(x,y)->max(abs$a-x)$abs$b-y)x,p))x
q[]=[]
q(x:y:z)=(x,y):q z
\$\endgroup\$
4
  • \$\begingroup\$ Is it less than than O(2^n)? \$\endgroup\$ – user unknown Aug 15 '11 at 22:37
  • \$\begingroup\$ No. The OP didn't require it to be less than O(n^2). \$\endgroup\$ – Thomas Eding Aug 15 '11 at 23:21
  • 1
    \$\begingroup\$ Last two sentences. I provided an O(n²)-solution myself before realizing it. And it isn't a golf-question, so avoiding whitespace and meaningful variable names isn't requiered. \$\endgroup\$ – user unknown Aug 16 '11 at 0:40
  • \$\begingroup\$ I didn't realize that posting non-golf puzzles was a part of this site. Eh, I'll keep my solution here. \$\endgroup\$ – Thomas Eding Aug 16 '11 at 18:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.