Abstract | ||
---|---|---|
We present efficient geometric algorithms for simplifying polygonal paths in R^2 and R^3 that have angle constraints, improving by nearly a linear factor over the graph-theoretic solutions based on known techniques. The algorithms we present match the time bounds for their unconstrained counterparts. As a key step in our solutions, we formulate and solve an off-line ball exclusion search problem, which may be of interest in its own right. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1016/j.comgeo.2004.09.003 | Comput. Geom. |
Keywords | Field | DocType |
computational geometry,off-line search,polygonal path,angle constraint,path simplification,graph-theoretic solution,known technique,time bound,linear factor,key step,own right,off-line ball exclusion search,polygonal path simplification,efficient geometric algorithm,line search | Combinatorics,Polygon,Computational geometry,Search problem,Polygonal chain,Mathematics | Journal |
Volume | Issue | ISSN |
32 | 3 | Computational Geometry: Theory and Applications |
Citations | PageRank | References |
9 | 0.69 | 19 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Danny Z. Chen | 1 | 1713 | 165.02 |
Ovidiu Daescu | 2 | 276 | 45.78 |
John E. Hershberger | 3 | 2146 | 213.79 |
Peter M. Kogge | 4 | 404 | 41.29 |
Ningfang Mi | 5 | 664 | 47.66 |
Jack Snoeyink | 6 | 2842 | 231.68 |