|
 ABSTRACT
In computational geometry, problems involving only rectilinear objects with edges parallel to the x -and y-axes have attracted great attention. They are often easier to solve than the same problems for arbitrary objects, and solutions are of high practical value, for instance in VLSI design. This is because in VLSI design technology requirements often dictate the use of only two orthogonal orientations for the boundary edges of objects as well as wires.
The restriction on the boundary edges motivates the study of rectilinear objects, while the restriction on wires brings the focus on the well-known L1-metric (the Manhattan distance). In short, given the two orthogonal orientations, both the shape of objects and the distance function are determined in a natural way.
More recent VLSI fabrication technology is capable of creating edges and wires in both the orthogonal and diagonal orientations. This motivates us to study more general polygons, and to generalize the distance concept to the case where any fixed set of orientations is allowed. We introduce a family of naturally induced metrics, and the subsequent generalization of geometrical concepts. A shortest connection between two points is in this case a path composed of line segments with only the given orientations. We derive optimal solutions for various basic planar distance problems in this setting, such as the computation of a Voronoi diagram, a minimum spanning tree, and the (minimum and maximum) distance between two convex polygons. Many other theoretically interesting and practically relevant problems remain to be solved. In particular, the new family of metrics may help bridge the gap between the L1- and the L2-metrics, as those are the limiting cases for two and infinitely many regularly distributed orientations.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
1. Bhattacharya, B. K., and G. T. Toussaint, "Efficient Algorithms for Computing the Maximum Distance between Two Finite Planar Sets," Journal of Algorithms 4, 1983, 121-136.
|
| |
2
|
2. Cheriton, R., and R. E. Tarjan, "Finding Minimum Spanning Trees," SIAM J. Comput. 5, 1976, 724-742.
|
| |
3
|
3. Chin, F., and C. A. Wang, "Optimal Algorithms for the Intersection and the Minimum Distance Problems between Planar Polygons," IEEE Trans. Comput. C-32, 1983, 1203-1207.
|
| |
4
|
4. Chin, F., and C. A. Wang, "Minimum Vertex Distance between Separable Convex Polygons," Info. Proc. Letters 18, 1984, 41-45.
|
| |
5
|
5. Edelsbrunner, H., "Intersection Problems in Computational Geometry," Institute für Informationsverarbeitung, Graz, Austria, Report F93, 1982.
|
| |
6
|
6. Edelsbrunner, H., "On Computing the Extreme Distances between Two ConvexPolygons", Institute für Informationsverarbeitung, Graz, Austria, Report F96, 1962.
|
 |
7
|
|
| |
8
|
8. Güting, R. H., "Conquering Contours: Efficient Algorithms for Computational Geometry," University of Dortmund, West Germany, 1983.
|
| |
9
|
|
| |
10
|
|
| |
11
|
11. Kirkpatrick, D., "Optimal Search in Planar Subdivisions," SIAM J. Comput. 12, 1963, 28-35.
|
| |
12
|
|
| |
13
|
13. Lee, D. T., and F. P. Preparata, "Computational Geometry: A Survey," IEEE Trans. Comput. C-33, 1984, 1072-1101.
|
| |
14
|
14. Lee, D. T., and C. K. Wong, "Voronoi Diagrams in L1(L¿) Metrics with 2-dimensional Storage Applications," SIAM J. Comput. 9, 1980, 200-211.
|
| |
15
|
15. McKenna, M., and G. T. Toussaint, "Finding the Minimum Vertex Distance Between Two Disjoint Convex Polygons in Linear Time," Technical Report No. SOCS 83.6, School of Computer Science, McGill University, 1983.
|
| |
16
|
16. Nicholl, T. M., Lee, D. T., Liao, Y. Z., and C. K. Wong, "On the X-Y Convex Hull of a Set of X-Y Polygons," BIT 23, 1983, 456-471.
|
| |
17
|
17. Ottmann, Th., Soisalon-Soininen, E., and D. Wood, "On the Definition and Computation of Rectilinear Convex Hulls," University of Waterloo, Report CS-83-07, 1983.
|
| |
18
|
18. Schwartz, J. T., "Finding the Minimum Distance between Two Convex Polygons," Info. Proc. Letters 13, 1981, 168-170.
|
| |
19
|
19. Sharnos, M. I., and D. Hoey, "Closest-point Problems," Proc. 16th Annual Symposium on Foundations of Computer Science, 1975, 151 -162.
|
| |
20
|
|
| |
21
|
21. Toussaint, G. T., and B. K. Bhattacharya, "Optimal algorithms for computing the minimum distance between two finite planar sets," Pattern Recognition Letters 2, 1983, 79-82.
|
| |
22
|
22. Toussaint, G. T., and J. A. McAlear, "A simple O(n log n) algorithm for finding the maximum distance between two finite planar sets," Pattern Recognition Letters 1, 1982, 21-24.
|
| |
23
|
|
CITED BY 3
|
|
|
|
|
Christian Icking , Rolf Klein , Ngoc-Minh Lê , Lihong Ma, Convex distance functions in 3-space are different, Proceedings of the ninth annual symposium on Computational geometry, p.116-123, May 18-21, 1993, San Diego, California, United States
|
|
|
Christian Icking , Rolf Klein , Lihong Ma , Stefan Nickel , Ansgar Weißler, On bisectors for different distance functions, Proceedings of the fifteenth annual symposium on Computational geometry, p.291-299, June 13-16, 1999, Miami Beach, Florida, United States
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
I.3