Paper Info
Title
On the bit complexity of minimum link paths: superquadratic algorithms for problem solvable in linear time
Abstract
All of the linear-time algorithms that have been developed for minimum-link paths use the real RAM model of computation. If one considers bit complexity, however, merely representing a minimum-link path may require a superquadratic number of bits. This paper considers bounds on the number of links (segments) needed by limited-precision approximations of minimum-link paths: When vertices are restricted to ‘‘first-derived’’ points, the number of links can increase by a constant factor; when they are restricted to points of an N×N grid, the number of links can increase by Θ log N . Keywords Simple polygons Link paths Exact geometric computation Grid geometry
Year
DOI
Venue
1996
10.1016/S0925-7721(98)00041-8
Selected papers from the 12th annual symposium on Computational Geometry
Keywords
Field
DocType
bit complexity,problem solvable,minimum link path,superquadratic algorithm,linear time
Real RAM,Discrete mathematics,Binary logarithm,Combinatorics,Vertex (geometry),Computer science,Algorithm,Approximations of π,Model of computation,Time complexity,Grid
Conference
Volume
Issue
ISSN
12
1
Computational Geometry: Theory and Applications
ISBN
Citations 
PageRank 
0-89791-804-5
13
0.84
References 
Authors
19
2
Name
Order
Citations
PageRank
Simon Kahan1279209.26
Jack Snoeyink22842231.68