|
hey, you should use a Delaunay triangulation. By definition, one of the stars that is coincident to a given star in the triangulation, call it MY_STAR, will be closest to MY_STAR. So your algorithm would be:
1. triangulate o(n lg n)
2. for each star, look at all coincident stars, and take the min distance
there are o(n) triangles, thus o(n) edges (another property of the Delaunay), so this step is o(n)
This should give you a loglinear solution, which seems optimal.
|
|
|
|
|
Wouldn't it be an O(n) operation to simply compute the distance of every single star, then select the minimum?
--- Modified realization
Oh, sorry. I didn't notice that he wants to find the closest star to ALL the other stars. I thought he was just looking for the closest star to a particular point.
Sounds like somebody's got a case of the Mondays
-Jeff
modified on Monday, January 21, 2008 3:24:22 PM
|
|
|
|
|
Hello,
I have a function that takes three variables and gives back two variables. Something like (a,b) = f(x,y,z). I'd like f to be like a look-up table. This means that I do not have mathematical representation of f. So the question is how do I represent such a look-up table efficiently, given that I would like to have an interpolation between existing values.
In 2d case when I have a = f(x) I can represent f as a bezier curve (which I can create and edit manually). And when I load it up I create a map m[x] gives me a. I use interpolation if x is not in the map.
My solution so far is based on 2d case, which means that I have a map like that m[x][y][z] (basically map of map of map of a pair (a,b)).
Is there a library that works with such issues in C++? Something that already provides similar functionality efficiently? I'd like to be able to create f(x,y,z), save it, load it and use it.
Thanks a lot.
|
|
|
|
|
It depends wether your f needs to have specific properties.
In the most simple case you can use linear interplation over both componentes (a and b) (just like you interpolate 3d-surfaces with triangulation / polygons ).
If f should be C^1, C^2, ... things get nasty and you might have to use some powerfull numerical interpolation methods.
Even in the most basic case you would have to find the 4 closest fixed points (see the other thread on this forum) and linear interpolate on those.
|
|
|
|
|
Thanks CKing! In my particular case linear interpolation is sufficient. I'd like to see if there is a library that deals with similar issues so I can reuse it.
Thanks.
Regards,
Alexander.
|
|
|
|
|
hello friends,
i read the algorithm to find Longest Monotone Subsequence which helps to find the Monotone increasing subsequence in a set of numbers in a list..
will u plz explain the concept of it..
|
|
|
|
|
|
hi there,
i am doing a application to demonstrate communication could be possible without encryption.. i refered to many articles and it is said it is possible by means of qkd.. can any1 suggest me a good algorithm for that.. it has to b easy to implement also. cos have to complete it b4 feb 2nd week.
helps of any form are welcome...
Thank u,
Freak8802
|
|
|
|
|
I'm not sure what you're trying to ask. Almost all communication is done unencrypted. If by QKD you're referring to using Quantum Key Distribution to have unbreakable encryption, I hope you have a 6 figure budget because the hardware needed to do it is anything but cheap. I also suspect there's a rather long lead time on the manufacturing of the QKD boxes. Alternatively with a research grade photonics lab you could try and make your own, but I don't think that'd be viable in only 2.5 months.
--
Join the Campaign to Help Stamp Out and Abolish Redundancy
The preceding is courtesy of the Bureau of Unnecessarily Redundant Repetition Department.
|
|
|
|
|
i shud have put myself clear then.. i have no idea in this regard.. i just no they have to be done with quantum encryption not any mathematical encryption.. can u guide if u have any src in this regard..
help of any kind are welcome..
Thank u,
Freak8802
|
|
|
|
|
QKD isn't encryption in and of itself. What it is, is a way to create and exchange one time pad keys (random numbers each used to encrypt a single byte and never used again). Due to the low bandwidth of current systems the OTPs are not used directly to encrypt the data but are instead used to exchange really long keys for symmetric encryption keys that are used over normal highspeed communication channels. The QKD hardware is used to provide new keys frequently enough that each symetric key isn't used for long enough to allow for pattern analysis to break it.
The QKD is done using expensive hardware ($100k and up last time I looked), and IS NOT something that can be implemented in software alone.
--
Join the Campaign to Help Stamp Out and Abolish Redundancy
The preceding is courtesy of the Bureau of Unnecessarily Redundant Repetition Department.
|
|
|
|
|
dan neely wrote: The QKD is done using expensive hardware ($100k and up last time I looked)
I think that is on the low side, too. Just for starters.
"The clue train passed his station without stopping." - John Simmons / outlaw programmer
|
|
|
|
|
Do you have access to lasers and stuff like that ? What about photon polarity and the Heisenberg uncertainty principle ? what about Bob and Alice ?
From what I understand, it's a lot more than just source code; and probably what is available right now must be under lock and key in the hands of a few companies and research departments around the world.
|
|
|
|
|
Ordinary lasers won't due. You need ones that are capable of emitting a single photon at a controlled polarization. The actual algorithm used isn't complex and could be simulated easily enough but would not be secure since the inability to be eavesdropped on is fundamental to the quantum nature of the data transfer.
--
Join the Campaign to Help Stamp Out and Abolish Redundancy
The preceding is courtesy of the Bureau of Unnecessarily Redundant Repetition Department.
|
|
|
|
|
Agreed and those kind of lasers are probably not sold at Circuit City.
|
|
|
|
|
Maximilien wrote: those kind of lasers are probably not sold at Circuit City
Probably not at Fry's Electronics, either :->
"The clue train passed his station without stopping." - John Simmons / outlaw programmer
|
|
|
|
|
Maximilien wrote: Heisenberg uncertainty principle ?
Alright, I've got to google that.
Maximilien wrote: what about Bob and Alice ?
Just hope they are on good terms with each other. Now, nobody point lasers at anybody's eyes 
"The clue train passed his station without stopping." - John Simmons / outlaw programmer
|
|
|
|
|
Well technically thats still encryption then.
Lloyd J. Atkinson
"Logic will get you from A to B, but imagination will take you everywhere" -ALbert Einstein
|
|
|
|
|
dan neely wrote: I hope you have a 6 figure budget because the hardware needed to do it is anything but cheap.
No kidding. 
"The clue train passed his station without stopping." - John Simmons / outlaw programmer
|
|
|
|
|
i think it can be done virtually in a computer.. i googled my doubts and i got good results.. it is said that it can be done virtually without the use of photons.. we need to encrypt the messages with different qubits.. which is defined by the representation of the bits which need to be sent.. all we have to do is to make an hidden channel.. but i got no clue how to do that????
can any1 who understood the above concept explain me???
Help of any kind r welcome....
Thank u,
Freak8802
|
|
|
|
|
You need a computer that stores information as qubits, not mere bits, otherwise it's not quantum at all. AND, there are only two implementations, and they both use photons - one uses polarization, the other entanglement. It's not just a software thing - not just any computer can do it.
You obviously have no idea about this, and quantum computing isn't for the faint-hearted, or the clueless. And anyway, QKD is tied-in with encryption, so basically it's not what you're looking for at all.
|
|
|
|
|
FREAK8802 wrote: i am doing a application to demonstrate communication could be possible without encryption
Well, you've just communicated something without encryption. What else you want to demonstrate ?
|
|
|
|
|
Be aware, maybe a misterious message is encrypted whitin.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
|
|
|
|
|
CPallini wrote: maybe a misterious message is encrypted whitin
And I wonder what that could be
"The clue train passed his station without stopping." - John Simmons / outlaw programmer
|
|
|
|
|
hello All,
Do anybosy have some idea of Rinjdael algorithm
neema jain
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
