Name
Abstract | ||
|---|---|---|
We consider the problem of two-dimensional output- sensitive convex hull in the cache-oblivious model. That is, we are interested in minimizing the number of cache faults caused when computing the convex hull of a set of N points on a plane. We are interested in the output- sensitive case where number of cache misses are ana- lyzed in the worst case based on both the input size N and output size H (number of extreme points that lie on the flnal convex hull ). There is the lower bound of N B log M B H B to match where M is the cache size and B is the block size. We present a simple algorithm which almost matches this lower bound. The number of cache misses our algorithm causes is |
Year | Venue | Keywords |
|---|---|---|
2007 | CCCG | convex hull,lower bound,extreme point |
Field | DocType | Citations |
Orthogonal convex hull,Discrete mathematics,Cache-oblivious algorithm,Combinatorics,Convex combination,Convex set,Convex hull,Convex polytope,Output-sensitive algorithm,Gift wrapping algorithm,Mathematics | Conference | 0 |
PageRank | References | Authors |
0.34 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peyman Afshani | 1 | 256 | 23.84 |
| Arash Farzan | 2 | 136 | 11.07 |