Name
Abstract | ||
|---|---|---|
With a system of parallel coordinates, objects in RN can be represented with planar “graphs” (i.e., planar diagrams) for arbitrary N [21]. In R2, embedded in the projective plane, parallel coordinates induce a point ← → line duality. This yields a new duality between bounded and unbounded convex sets and hstars (a generalization of hyperbolas), as well as a duality between convex union (convex merge) and intersection. From these results, algorithms for constructing the intersection and convex merge of convex polygons in O(n) time and the convex hull on the plane in O(log n) for real-time and O(n log n) worst-case construction, where n is the total number of points, are derived. By virtue of the duality, these algorithms also apply to polygons whose edges are a certain class of convex curves. These planar constructions are studied prior to exploring generalizations to N-dimensions. The needed results on parallel coordinates are given first. |
Year | DOI | Venue |
|---|---|---|
1987 | 10.1145/31846.32221 | J. ACM |
Keywords | Field | DocType |
verification additional key words and phrases: computational geometry and object modeling,convex hull,general terms: algorithms,unbounded convex set,convex curve,convexity algorithm,n log n,duality,convex polygon,log n,convexity,parallel coordinates,multidimensional coordinates,planar construction,line duality,convex union,new duality | Discrete mathematics,Combinatorics,Convexity,Computer science,Planar,Parallel coordinates,Projective plane,Planar graph | Journal |
Volume | Issue | ISSN |
34 | 4 | 0004-5411 |
Citations | PageRank | References |
18 | 20.34 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alfred Inselberg | 1 | 1230 | 165.81 |
| Mordechai Reif | 2 | 18 | 20.34 |
| Tuval Chomut | 3 | 18 | 20.34 |