Loading...
Please wait, while we are loading the content...
Similar Documents
On the Complexity of the convex Hull problem under a RAM variant model
| Content Provider | Semantic Scholar |
|---|---|
| Author | Abdulla, Mirza |
| Copyright Year | 2018 |
| Abstract | We consider a variant model of computation from the RAM model where the access cost to memory is not constant but according to a non-decreasing function. This change makes the model more reflective of the performance of algorithms on computers used in practice as it captures the cost of data movement and consequently force the capitalization of memory reference in order to obtain efficient algorithms. We show that for geometric problems such as the planar convex hull problem where we are given n points in the plane and asked to find the smallest area polygon that encompasses all n points that we can still get optimal time bounds without scarifying the space bounds. |
| Starting Page | 35 |
| Ending Page | 45 |
| Page Count | 11 |
| File Format | PDF HTM / HTML |
| DOI | 10.23956/ijarcsse.v8i11.868 |
| Volume Number | 8 |
| Alternate Webpage(s) | http://www.ijarcsse.com/index.php/ijarcsse/article/download/868/515 |
| Alternate Webpage(s) | https://doi.org/10.23956/ijarcsse.v8i11.868 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
