{"action":"created","issue":{"url":"https://api.github.com/repos/mlpack/mlpack/issues/642","repository_url":"https://api.github.com/repos/mlpack/mlpack","labels_url":"https://api.github.com/repos/mlpack/mlpack/issues/642/labels{/name}","comments_url":"https://api.github.com/repos/mlpack/mlpack/issues/642/comments","events_url":"https://api.github.com/repos/mlpack/mlpack/issues/642/events","html_url":"https://github.com/mlpack/mlpack/issues/642","id":156323812,"number":642,"title":"Neighbor Search - Incorrect bound.","user":{"login":"MarcosPividori","id":4282009,"avatar_url":"https://avatars.githubusercontent.com/u/4282009?v=3","gravatar_id":"","url":"https://api.github.com/users/MarcosPividori","html_url":"https://github.com/MarcosPividori","followers_url":"https://api.github.com/users/MarcosPividori/followers","following_url":"https://api.github.com/users/MarcosPividori/following{/other_user}","gists_url":"https://api.github.com/users/MarcosPividori/gists{/gist_id}","starred_url":"https://api.github.com/users/MarcosPividori/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MarcosPividori/subscriptions","organizations_url":"https://api.github.com/users/MarcosPividori/orgs","repos_url":"https://api.github.com/users/MarcosPividori/repos","events_url":"https://api.github.com/users/MarcosPividori/events{/privacy}","received_events_url":"https://api.github.com/users/MarcosPividori/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":2,"created_at":"2016-05-23T17:38:49Z","updated_at":"2016-05-23T20:34:03Z","closed_at":null,"body":"Hi, @sumedhghaisas  @rcurtin \r\nI have been reading the paper: \"Tree-Independent Dual-Tree Algorithms\" in detail, and I found an error in the definition of bound B2. I attach a pdf file with an explanation using latex, so it is easier to understand what I mean.\r\nI think it won't be difficult to update the code to fix this.\r\nIf you agree on this modification, I can work on this and make pull request when it is fixed.\r\nThanks,\r\nMarcos\r\n[bounds.pdf](https://github.com/mlpack/mlpack/files/277943/bounds.pdf)\r\n"},"comment":{"url":"https://api.github.com/repos/mlpack/mlpack/issues/comments/221087748","html_url":"https://github.com/mlpack/mlpack/issues/642#issuecomment-221087748","issue_url":"https://api.github.com/repos/mlpack/mlpack/issues/642","id":221087748,"user":{"login":"sumedhghaisas","id":5289793,"avatar_url":"https://avatars.githubusercontent.com/u/5289793?v=3","gravatar_id":"","url":"https://api.github.com/users/sumedhghaisas","html_url":"https://github.com/sumedhghaisas","followers_url":"https://api.github.com/users/sumedhghaisas/followers","following_url":"https://api.github.com/users/sumedhghaisas/following{/other_user}","gists_url":"https://api.github.com/users/sumedhghaisas/gists{/gist_id}","starred_url":"https://api.github.com/users/sumedhghaisas/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sumedhghaisas/subscriptions","organizations_url":"https://api.github.com/users/sumedhghaisas/orgs","repos_url":"https://api.github.com/users/sumedhghaisas/repos","events_url":"https://api.github.com/users/sumedhghaisas/events{/privacy}","received_events_url":"https://api.github.com/users/sumedhghaisas/received_events","type":"User","site_admin":false},"created_at":"2016-05-23T20:34:03Z","updated_at":"2016-05-23T20:34:03Z","body":"So about the situation you mentioned where the child's B2 bound is calculated using the tighter bound. You mentioned that rho(c) + lambda(c) < 2 * lambda(c). I don't think this can happen. So if I understand correctly lambda is a max distance from centroid of convex subset to points held in the node where as rho is a max distance from centroid of convex subset to all descendant points of that node which also includes the points held in that node. So clearly we get that rho(c) >= lambda(c). This can be proved through contradiction. If rho(c) is < lambda(c) then we know that there is some point in the points held by the node who's distance from centroid id more hence rho(c) is indeed incorrect and will become equal to lambda(c). So assuming I have not made any incorrect assumption while reading the paper :) the current implementation will stand correct. However, your observation is correct, that while deriving the recursive definition both bounds are used. I will have to go through that derivation and see the reasons behind it or if better bound can be achieved. "}}
{"actor":{"display_login":"sumedhghaisas"}}