Convex hull trick
From PEGWiki
Revision as of 05:37, 2 January 2010 by Brian (Talk | contribs) (Created page with 'The '''convex hull trick''' is a technique which is perhaps best known in algorithm competition from being required to obtain full marks in several USACO problems, such as [http:…')
The convex hull trick is a technique which is perhaps best known in algorithm competition from being required to obtain full marks in several USACO problems, such as MAR08 "acquire", which began to be featured in national olympiads after its debut in the IOI '02 task Batch Scheduling, which itself credits the technique to a 1995 paper (see references). Very few online sources mention it, and almost none describe it. (The technique might not be considered important enough, or people might want to avoid providing the information to other countries' IOI teams.)
References
- Brucker, P. (1995). Efficient algorithms for some path partitioning problems. Discrete Applied Mathematics, 62(1-3), 77-85.
