TY - JOUR

T1 - Experiments on the practical I/O efficiency of geometric algorithms

T2 - Distribution sweep versus plane sweep

AU - Chiang, Yi Jen

N1 - Funding Information:
Keywords: Segment intersection; Plane sweep; Distribution sweep; B-tree; External-memory algorithm; Implementation; Experimentation; Probabilistic analysis An extended abstract of this paper was presented at the 4th Workshop on Algorithms and Data Structures, Kingston, Ontario, Canada, August 1995. This work was conducted when the author was at the Computer Science Department of Brown University. Research supported in part by the National Science Foundation, by the U.S. Army Research Office, and by the Office of Naval Research and the Advanced Research Projects Agency. i E-maih yjc@ams.sunysb.edu.

PY - 1998/3

Y1 - 1998/3

N2 - We present an extensive experimental study comparing the performance of four algorithms for the following orthogonal segment intersection problem: given a set of horizontal and vertical line segments in the plane, report all intersecting horizontal-vertical pairs. The problem has important applications in VLSI layout and graphics, which are large-scale in nature. The algorithms under evaluation are our implementations of distribution sweep and three variations of plane sweep. Distribution sweep is specifically designed for the situations in which the problem is too large to be solved in internal memory, and theoretically has optimal I/O cost. Plane sweep is a well-known and powerful technique in computational geometry, and is optimal for this particular problem in terms of internal computation. The three variations of plane sweep differ by the sorting methods (external versus internal sorting) used in the preprocessing phase and the dynamic data structures (B-tree versus 2-3-4-tree) used in the sweeping phase. We generate the test data by three programs that use a random number generator while producing some interesting properties that are predicted by our theoretical analysis. The sizes of the test data range from 250 thousand segments to 2.5 million segments. The experiments provide detailed quantitative evaluation of the performance of the four algorithms, and the observed behavior of the algorithms is consistent with their theoretical properties. This is, to the best of our knowledge, the first experimental algorithmic study comparing the practical performance between external-memory algorithms and conventional algorithms with large-scale test data.

AB - We present an extensive experimental study comparing the performance of four algorithms for the following orthogonal segment intersection problem: given a set of horizontal and vertical line segments in the plane, report all intersecting horizontal-vertical pairs. The problem has important applications in VLSI layout and graphics, which are large-scale in nature. The algorithms under evaluation are our implementations of distribution sweep and three variations of plane sweep. Distribution sweep is specifically designed for the situations in which the problem is too large to be solved in internal memory, and theoretically has optimal I/O cost. Plane sweep is a well-known and powerful technique in computational geometry, and is optimal for this particular problem in terms of internal computation. The three variations of plane sweep differ by the sorting methods (external versus internal sorting) used in the preprocessing phase and the dynamic data structures (B-tree versus 2-3-4-tree) used in the sweeping phase. We generate the test data by three programs that use a random number generator while producing some interesting properties that are predicted by our theoretical analysis. The sizes of the test data range from 250 thousand segments to 2.5 million segments. The experiments provide detailed quantitative evaluation of the performance of the four algorithms, and the observed behavior of the algorithms is consistent with their theoretical properties. This is, to the best of our knowledge, the first experimental algorithmic study comparing the practical performance between external-memory algorithms and conventional algorithms with large-scale test data.

KW - B-tree

KW - Distribution sweep

KW - Experimentation

KW - External-memory algorithm

KW - Implementation

KW - Plane sweep

KW - Probabilistic analysis

KW - Segment intersection

UR - http://www.scopus.com/inward/record.url?scp=0042853208&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0042853208&partnerID=8YFLogxK

U2 - 10.1016/S0925-7721(97)00020-5

DO - 10.1016/S0925-7721(97)00020-5

M3 - Article

AN - SCOPUS:0042853208

SN - 0925-7721

VL - 9

SP - 211

EP - 236

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 4

ER -