Name
Abstract | ||
|---|---|---|
A common geometric problem in computer graphics and geographic information systems is to compute the arrangement of a set of n segments that can be colored red and blue so that there are no red/red or blue/blue crossings. We give a sweep algorithm that uses the minimum arithmetic precision and runs in optimal O(n log n + k) time and O(n) space to output an arrangement with k vertices, or O(n log n) time to determine k. Our initial implementation in Java can be found at http:\\www.cs.unc.edu\~snoeyink\demos\rbseg. |
Year | Venue | Keywords |
|---|---|---|
2000 | JCDCG | minimum arithmetic precision,common geometric problem,geographic information system,optimal time,k vertex,blue line segments,intersecting red,optimal o,blue crossing,n log n,n segment,computer graphics,initial implementation,computer graphic,information system |
Field | DocType | Volume |
Discrete mathematics,Line segment,Colored,Vertex (geometry),Computer science,Algorithm,Problem complexity,Time complexity,Computer graphics,Java | Conference | 2098 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-42306-0 | 1 |
PageRank | References | Authors |
0.36 | 17 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrea Mantler | 1 | 82 | 6.54 |
| Jack Snoeyink | 2 | 2842 | 231.68 |