Closed

Fast Nearest neighbor + sphere query data structures

There are two data structures I'd like made, they are pretty similar but I will describe them separately

They will have to be implemented in lua 5.1 for the Roblox game engine, but it is okay if you are not familiar with it because I can help with the implementation

So specifications on the first data structure that accelerates building object queries:

1. be designed for 3 dimensions

2. fast insertion/deletion (poly log?) with weights if possible (if not possible, then priority tiers/using many versions of the data structure to represent the priority tiers)

3. k nearest neighbors with euclidean distance--but after finding each neighbor I'd like to decide whether to stop the search or continue O(poly log(n)+k)

4. sphere queries: find which buildings are in a sphere with radius R centered at position O

5. if it is a lot easier, each building can be treated as a set of cells where each cell is the same size and occupied by at most one building

6. if possible, I'd like to restrict the search bounds on the y coordinate--if this is not possible, we'll probably need to create a new version of the data structure for each y group

7. the x and z axes sizes and cell size are constant, the y changes rarely and only increases, it would be nice to resize the data structure but I am okay with recreating a new structure at n*poly log cost

8. this data structure needs to be extremely practical, and in lua 'tables' (arrays/dictionaries/hash maps/structs) can be expensive, so it would be nice to fit it into an array (taking advantage of #7)

Specifications on the second data structure that accelerates actor queries:

**means I appended/changed from first

1. be designed for 3 dimensions

2. fast insertion/deletion (poly log?) with weights if possible (if not possible, then priority tiers/using many versions of the data structure to represent the priority tiers)

**2.5. fast updating (though this can just be insert+delete)

3. k nearest neighbors with euclidean distance--but after finding each neighbor I'd like to decide whether to stop the search or continue O(poly log(n)+k)

4. sphere queries: find which actors are in a sphere with radius R centered at position O

**5. each actor is represented as (ordered from best to worst) capsule, cylinder, cuboid, sphere, point

**5.5. there are no cells here (but hopefully actors never intersect each other)

6. if possible, I'd like to restrict the search bounds on the y coordinate--if this is not possible, we'll probably need to create a new version of the data structure for each y group

**7. if it is easier we can assume the map extents are forever constant

8. this data structure needs to be extremely practical, and in lua 'tables' (arrays/dictionaries/hash maps/structs) can be expensive, so it would be nice to fit it into an array (taking advantage of #7)

Skills: C++ Programming, C Programming, C# Programming, Algorithm, Lua

About the Employer:
( 0 reviews ) Los Gatos, United States

Project ID: #20377949

7 freelancers are bidding on average $536 for this job

JinDongZhe

Cool Client! I am full stack developer such as react-native(ios,android) ,laravel, CI and backend. Thank you for your job posting. I read your project very carefully. I'm a senior React Native expert with several years More

$800 USD in 7 days
(92 Reviews)
6.4
avto35217

Hi,sir. I am super interested in your project - 'Fast Nearest neighbor + sphere query data structures' :) I believe that my 12+ years of experience in development makes me highly qualified for this project. I'm sure th More

$555 USD in 2 days
(11 Reviews)
4.3
shingjin

Dear Client. First of all, it's my pleasure to bid on your project. I am very interested in your proposal. Because I have rich experience in this field. If you choose me, you'll never be disappointed in me, and I'll do More

$500 USD in 7 days
(12 Reviews)
3.8
MichealSMoreno

Dear client, how have you been? I've read your project description carefully. I'm fully aware of algorithms and flexible to customize them. I'd like to know the limitations more. How about discuss in chat? Waiting for More

$400 USD in 20 days
(8 Reviews)
3.4
SmithZhang

Hi, sir. I am C++ Programing expert and database design expert that have rich experience for 10+ years. I am very interested in your description. As you mentioned, your two specification about data structure are very s More

$500 USD in 7 days
(2 Reviews)
1.3
ProgramICO

Hello I am a senior developer so i can do it very easily if you want. Contact me right now i am ready to start this project for you. Low cost and high quality result reply to discuss more about this project

$500 USD in 7 days
(2 Reviews)
2.1
blackwhite123

Hello, I am pleasure with your job for Fast Nearest neighbor + sphere query data structures. Thank you for the job posting. It’s a pleasure to meet you. I’d really like to work with you on this one if possible! I do ha More

$500 USD in 7 days
(0 Reviews)
0.0