Hacker News new | past | comments | ask | show | jobs | submit login
Ask HN: I just discovered a new algorithm. What should I do?
80 points by 0xfaded on Aug 27, 2017 | hide | past | favorite | 54 comments
Hi HN,

For a robotics problem I have, I needed to determine the minimum distance between a point and an ellipse.

Existing stack overflow answers suggest using root finders to solve a quartic equation or specialised iterative methods that have instabilities.

https://stackoverflow.com/questions/22959698/distance-from-given-point-to-given-ellipse

One paper suggests using an initial guess on the ellipse as a root of the quartic, using the guess to simplify it to a cubic, and then solving it. The result is a fast converging stable algorithm, but solving the cubic and choosing the correct root is gross.

I've come up with a method that relies on maths that most programmers would not be familiar with, but the implementation boils down to 14 lines of python. It converges quickly (3 iterations) and is completely robust (no divergences or divide by zeros).

This is the first time I've been sitting on an algo that I genuinely believe to be novel. The robotics is a side project and work doesn't lay claim to IP outside of work.

I intend to write up a blog post tomorrow, but if you were in my shoes what would you do?

Thanks




There're a lot of people here telling you how to "protect" your idea, and a lot of people telling you that it's probably not novel. I just wanted to comment and congratulate you on figuring out a method that's novel to you; it's a legitimate discovery for you and should be celebrated even if someone else has already found it.


Stack overflow has lots of great programming answers, but is by no means an exhaustive research resource for algorithms. Have you looked through the ray tracing literature? Good table on various geometry intersection algorithms here: http://www.realtimerendering.com/intersections.html

Other search terms you might not have tried: "ray-object intersection", "ray-ellipse intersection", "line-ellipse intersection". Also check for "ellipsoid" algorithms, there might be something in 3d that can simplify to 2d.

Oh, also try looking through video game physics sites, tons of minimum distance, path planning, and collision algorithms. Many physics engines are open source, there might be some distance-to-ellipse code publicly available. http://www.tapirgames.com/blog/open-source-physics-engines

Edit: deleted my algorithm that won't work suggestion. :P

PS: there's probably no reason not to do a blog post, there might only be reasons not to claim it's novel, even if you don't know it yet. You might want to write it up without claiming novelty as part of your search to figure out if it's new. You could still publish it formally later.


Write a blog post. Don't waste time doing a more exhaustive search of the literature, but also don't go too heavy on the claims that it's totally novel. Novelty might matter for an academic publication, but it's completely irrelevant for a blog post. You had a problem to solve, didn't like the solutions you could find, and came up with something better. That's what matters, not whether it was already first published 50 years ago.

One of the more popular things I ever posted was just pointing out a an implementation trick for a data structure that was known but not widely used. Why would the readers care that it wasn't novel? What they cared about was a) that they didn't already know about it, b) after reading the post they could understand why this was a useful/interesting optimization.


"Write a blog post. Don't waste time doing a more exhaustive search of the literature".

No wonder the Internet has such a low SNR.


Implying that the original poster's blog post is going to be lowering the SNR of the Internet is a really shitty thing to say.

There are four options:

1. This is a truly novel. The author writes a blog post.

2. This is not novel. The author finds some prior art, and writes a blog post about his own work but referencing the earlier work.

3. This is not novel. The author doesn't find out, and writes a blog post. Someone possibly responds pointing them to the relevant prior art.

4. This is not novel. The author finds the earlier research, is discouraged, and decides not to write a blog post.

The only bad option here is 4. So exactly what is additional research going to achieve at this point? (There is of course a point to doing the research before inventing your own algorithm. Or you can do it because this kind of CS archaeology is fun. But it doesn't really have a lot of value).


https://arxiv.org/

As suggested here, perhaps consider writing up and submitting a short article to arxiv. That ought to be enough to ensure credit. If you don't intend to patent it (don't know where you are located & local laws), the arxiv preprint service will give you a citable, dated & externally validated submission that you can use. It wouldn't be peer reviewed until you submit it to an appropriate journal, but that's a relatively short step away once you upload the preprint to arxiv.


Do you need a referral to submit to arxiv? I recall when wanting to submit a paper there a few years ago you had to get someone who's already published to vouch for you. Am I reading correctly?


Yes.

https://arxiv.org/help/submit


If you care about citation count without the hassle of publishing a paper, you should make the blog post or github repo easy to cite.

Add a blurb along the lines of "For attribution in academic contexts, please cite this work as: (insert bibtex blob here)".

For examples, see the bottom of the posts distill.pub: https://distill.pub/2017/momentum/#citation. Or bottom of academic github repositories such as: https://github.com/sympy/sympy#citation.


You should make sure it's actually new. Study the literature carefully -- it may have already been discovered and published. Google Patents https://www.google.com/?tbm=pts is also a good place to look. It's also worth digging into existing scientific mathematics libraries like GSL as well as other space simulation libraries like mantissa to see if they implemented it.

If you are just looking to put your name publicly on it, it's oftentimes good enough just to write a blog post and make a wheel. That way you can always point to it later and build a google presence. If you are looking to possibly patent the algorithm, talk to a good IP attorney specializing in software patents.


Find a friendly CS professor familiar with the problem domain and share your solution. They can help determine if it's correct, if it's truly novel and if it is, help you write a paper and get it peer reviewed.


This seems like a great way to get your work appropriated by said "friendly" professor, especially if you're coming out of the woodwork and thus don't have a credible paper trail documenting the process of your discovery, etc.

I quite prefer approaches of private publishing that can be demonstrated to have been publicized before said professor chooses to "help".


I may be naive, but I don't think professors would typically do that, certainly not if you offer them to be a co-author in exchange for professionalizing the paper (which may mean serious work, e.g. to benchmark the algorithm against other algorithms for speed and accuracy). Even if you don't offer that, they will have a few months to work on follow-up papers (e.g. on I mplementing it on GPUs, in parallel, or on simple architectures)

You can also publish (e.g. by tweeting it) a hash (a few different hashes, if you are truly paranoid) of your code before going to said professor. That gives you some leverage against appropriation, as it would allow you to prove you knew about the approach at a given time.

If you combine it with some context ("going to meet X to discuss 0xA43AF7F963DA003F"), that leverage gets larger. I wouldn't know whether either would be enough, though. There likely is little jurisprudence on things like this, it may be costly to go to court over it, and using it out of court, e.g. by writing to any journal publishing this without your name on it, may backfire)


Update:

Blog post has been published

http://wet-robots.ghost.io/simple-method-for-distance-to-ell...

https://news.ycombinator.com/item?id=15114026


Congratulations!

I'd definitely write up a blog post. If you find the feedback confirms the originality, you might then consider writing a short paper for arXiv. After that, sprinkle appropriate references in StackOverflow, Wikipedia, etc. so folks can find your work.

If you are in the US, I would not spend any time or energy trying to figure out a patent. With the "Alice" ruling [1] in 2014, the Supreme Court has effectively said that algorithms and business methods that are performed just "....on a general purpose computer" are not patentable.

Also, should you get a patent, then what? Royalties to individual inventors w/o actually developing and selling a product...it virtually never happens.

[1] https://en.wikipedia.org/wiki/Alice_Corp._v._CLS_Bank_Intern...


Getting a patent is an expensive business. Patentability of methods of manipulating numbers is variable around the world, but in most places its not going to work. You might have managed it in the US a few years ago, but not now. Seriously applying for a patent is not cheap. The odds are that you will spend a lot of money for no return.

Getting priority for something on your CV is another matter. As others have mentioned, write up a paper and submit to arxiv.org.

Incidentally, are you aware of this: http://www.mathpages.com/home/kmath505/kmath505.htm

The last couple of paragraphs describe a geometric construction giving an approximation that is good enough for many purposes, and would also be the right starting point for any iterative algorithm.


> I've come up with a method that relies on maths that most programmers would not be familiar with

I'm curious about the kind of math you have used for solving the problem.


Yeah me too, I recall reading about solving this exact problem pretty recently, bring out the goods!


That would very much depend on your goal. Do you just want credit, do you want to try to monetize the algorithm, or something else entirely?


Good points. I'm not particularly interested in monetizing the algorithm.

I think I'd like to be able to point to it the next time I go for job interviews. Another possible goal would be to try publish something formally to help with an O visa (or international equvilent) should I ever need one.

Thanks


Great goals, as others suggested: depending on what side of the field it falls to, post to https://cs.stackexchange.com/ or https://mathoverflow.net/ and ask for help improving and whether it's original and mention you'd like to publish although the latter is off topic there. Or you can try to email me at chx1975 gmail and I will ask my high school classmates whether they know anyone who would be helpful. They will. It was that sort of high school. Some became very high level game developers some became lecturers and associate professors and so on.


A lot of people are telling you to check whether your idea really is novel. You should probably do that, but even if you find out that someone else has already published it, not all is lost.

If your derivation is different (hopefully simpler) and you do additional analysis (e.g. of numerical stability), you could still get a publication out of it. (Probably not in a top journal, but better than a paper mill.)

Disclaimer: I have not published any papers myself, but I have read papers that were essentially "The method presented in X et al. is useful, but we didn't get the explanation until we rediscovered it ourselves. Here is a more understandable derivation.".


I’d ask my employer for permission, then I’d write a blog post.

P.S. Have you seen this? https://www.geometrictools.com/GTEngine/Include/Mathematics/...

https://www.geometrictools.com/Documentation/DistancePointEl...


Why would you ask your employer for permission? Permission to do what, write your own blog post?


The OP’s question was “if you were in my shoes what would you do?”

I don’t invent stuff like that in my spare time. I do that because an employer or client paid me for R&D.

That’s why I would ask for permission first.


OP here, I just woke up to some exceptional advice, thank you all.

I agree most with the "blog and litter stack overflow with references approach". This accomplishes the goals of making what I have useful and discoverable by others, and giving myself something to point to in the future.

I'll comment here and post it to HN when its ready. If it gets enough viewership here and the advice becomes to publish a small article, I'll then do that.

Thanks again.


Have you studied Numerical Analysis? There is an entire panoply of approximation methods, I highly doubt your method is entirely novel.


What do you expect to be able to do with it?

I'd say just publish an academic paper on it under your name.


I'm so out of my depth here it isn't even funny. Just wanted to say way to go...whether you indeed have something novel or not, thats awesome to even have a brush with such a thing.


In my experience, the method described here works very well in practice:

http://wwwf.imperial.ac.uk/~rn/distance2ellipse.pdf

(this is linked to from the stackoverflow post)

Finding the closest point for an ellipsoid is more challenging in practice, because one needs to take a different parametrization near a pole, and sometimes conjugate gradient is necessary to get convergence.


Although I didn't implement this myself, the plot accompanying the answer shows that if correctly implemented, this method is unstable in some regions inside the ellipse.


> This is the first time I've been sitting on an algo that I genuinely believe to be novel.

The odds are extremely high that you're simply mistaken. While it might be novel to programmers, it's very unlikely to be novel to mathematicians. Research maths for prior art, or write a paper and submit to a journal for peer review, someone will point out if it isn't novel, which it likely isn't.


Make it an open source module


Just write the blog post and enjoy your victory. Be as clear as possible and explain your process.

I had fun finding how to know quickly if a rectangle and a bezier curve intersect or not (back in 2005 I believe), it's a nice feeling to have.


Blog post is fine, but if you want to reach as many people as possible, I'd also post it as an answer on that Stack Overflow question. Since that's where most developers would look first when encountering that problem (yourself included, evidently).


Are you sure newton's method or conjugate gradient isn't going to solve this problem?


They would, however the implementation is now reduced to something you'd happily copy and paste into a code base. Part of what's novel is how the iterative step size is chosen. The Distance function can be very shallow in some cases, so if one wanted to use a root finder it would probably be wise to use an off the shelf implementation.


Numerical methods is an exceptionally well-researched area that saw lots of activity back when machines were weak and Fortran was the weapon of choice. It's more likely than not that what you discovered has been done before and/or it's trivially derived from a more generic algorihm.

Your best bet would probably be to re-run your search (including academic papers and not just stackoverlow, which is an inch deep) and ask around and see what prior art will surface.


If you want to do it properly, then you'd have to describe how the number of significant digits of the result grows in the number of iterations.


It sounds like you've done some research, but the fact you're citing stack overflow makes me wonder where you're at in that process (nothing wrong with stack overflow, but...)

Research the hell out of it. Google Scholar is pretty good, but if papers are behind paywalls and you can't get them elsewhere you might have to find library access somehow. Read original research papers and make sure it isn't covered elsewhere.

Stack Overflow and places like that are often good starts, but people often reinvent the wheel there, or make up things on the fly without being aware of research papers that go into much more depth.

If you're still convinced you have something novel, write it up as an academic paper and post it to arxiv, and then submit it to a peer-reviewed journal. Reviewers will let you know how novel it is.

You could also post it to arxiv and/or a journal, but my guess is you'll end up needing to cite the academic literature so you'll need to do that at some point.


if you think you have truly found something new -- and i must admit i was naturally skeptical at first, but you convinced me that you'd done _some_ homework -- then don't be discouraged by the people who say "it's probably not novel". maybe it's not, but people do discover new things every day. heck, the odds are that you will never win a half-a-billion dollars in a lottery, but last week a woman actually did.


I look forward to seeing your blog post. I would probably do the same. Very congratulations


Wait, do people really get so few ideas that they feel the need to celebrate each of them?


We detached this subthread from https://news.ycombinator.com/item?id=15111160 and marked it off-topic.


There's a difference between getting an idea, and developing a (potentially) novel algorithm to solve a non-trivial problem.


Many people have many ideas, very few people have novel ideas, so novel ideas are worth being proud of because they are very few and far between. (I have no idea if this particular idea is novel -- odds are against it though.)


This is satire on HN right?


The comments surely are.


I would mention it on IRC and then probably forget it. Maybe out the code in some pastebin for others to see.


Patent the idea, Publish a paper, submit it to a robotics conference. Some big company with deep pockets will buy the rights to your patent for a sum of money that will be large to you and small for them.


this is why we cant have nice things :/


Unbelievable this is downvoted. Do people not approve of the patent system? It has been in place for decades as a battle-tested way of incentivizing innovation and creates a natural process for getting trade secrets into the public domain.

The patent system allows small inventors / startups to be competitive with large monopolies. It creates a safe space for free innovation. What is wrong with that?

It's the equivalent of having laws against stealing. How could a shop keeper run a business if stealing was not illegal?


You can't patent math.


Then describe how you would implement it using CMOS logic.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: