Skip to main content
SpringerLink
Log in

Computing shortest transversals

Die Berechnung kürzester Transversalen

  • Published:
Computing Aims and scope Submit manuscript

Abstract

We present anO(nlog2 n) time andO(n) space algorithm for computing the shortest line segment that intersects a set ofn given line segments or lines in the plane. If the line segments do not intersect the algorithm may be trimmed to run inO(nlogn) time. Furthermore, in combination with linear programming the algorithm will also find the shortest line segment that intersects a set ofn isothetic rectangles in the plane inO(nlogk) time, wherek is the combinatorial complexity of the space of transversals andk≤4n. These results find application in: (1) line-fitting between a set ofn data ranges where it is desired to obtain the shortestline-of-fit, (2) finding the shortest line segment from which a convexn-vertex polygon is weakly externally visible, and (3) determing the shortestline-of-sight between two edges of a simplen-vertex polygon, for whichO(n) time algorithms are also given. All the algorithms are based on the solution to a new fundamental geometric optimization problem that is of independent interest and should find application in different contexts as well.

Zusammenfassung

Wir stellen einen Algorithmus zur Berechnung der kürzesten Strecke vor, welchen in der Ebene gegebene Geraden oder Strecken schneidet. Die Berechnung erfordertO(nlog2 n) Zeit undO(n) Platz. Falls sich die Strecken nicht schneiden, kann der Zeitbedarf aufO(nlogn) reduziert werden. In Verbindung mit Linearer Optimierung findet der Algorithmus auch die kürzeste Strecke, welchen isothetische Rechtecke schneidet. Hier ist der ZeitbedarfO(nlogk), wobeik die kombinatorische Komplexität des Raumes der Transversalen ist undk≤4n gelten muß. Mögliche Anwendungen der Ergebnisse sind: (1) Bestimmung der kürzestenPass-Linie fürn Datenbereiche, (2) Bestimmung der kürzesten Strecke, von welcher ein konvexesn-Polygon schwach sichtbar ist und (3) Bestimmung der kürzestenSichtlinie eines einfachenn-Polygons, wobei wir auchO(n)-Zeit Algorithmen angeben. Alle Algorithmen beruhen auf der Lösung einer grundlegenden geometrischen Optimierungsaufgabe. Diese ist von selbständigem Interesse und sollte weitere Anwendungen ermöglichen.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • [AB87] Atallah, M. J., Bajaj, C., Efficient algorithms for common transversals,Information Processing Letters, vol. 25 (1987), pp. 87–91.

    Google Scholar 

  • [AD90] Avis, D., Doskas, M., Algorithms for high dimensional stabbing problems,Discrete and Applied Mathematics, (in press).

  • [AGT86] Avis, D., Gum, T., Toussaint, G. T., Visibility between two edges of a simple polygon,The Visual Computer, vol. 2 (1986), pp. 342–357.

    Google Scholar 

  • [AHU83] Aho, A. V., Hopcroft, J. E., Ullman, J. D.,Data Structures and Algorithms, Addison-Wesley (1983).

  • [At86] Atallah, M. J., Computing the convex hull of line intersections,Journal of Algorithms, vol. 7 (1986), pp. 285–288.

    Google Scholar 

  • [AT81] Avis, A. Toussaint, G. T., An optimal algorithm for determining the visibility of a polygon from an edge,IEEE Transactions on Computers, vol. C-30, No. 12 (1981), pp. 910–914.

    Google Scholar 

  • [AW87] Avis, D., Wenger, R., Algorithms for line stabbers in space,Proc. 3rd ACM Symposium on Computational Geometry (1987), pp. 300–307.

  • [AW88] Avis, D., Wenger, R., Polyhedral line transversals in space,Discrete and Computational Geometry, vol. 3, No. 3 (1988), pp. 257–266.

    Google Scholar 

  • [BKT89] Bhattacharya, B. K., Kirkpatrick, D. G., Toussaint, G. T., Determining sector visibility of a polygon,Proc. 5th ACM Symposium on Computational Geometry, Saarbruchen (1989), pp. 247–254.

  • [BL83] Bajaj, C., Li, M., On the duality of intersection and closest points,Proc. 21st Allerton Conference (1983), pp. 459–461.

  • [BT91] Bhattacharya, B. K. and Toussaint, G. T., “Computing the wingspan of a butterfly,” manuscript in preparation.

  • [BV76] Buchman, E., Valentine, F. A., External visibility,Pacific Journal of Mathematics, vol. 64 (1976), pp. 333–340.

    Google Scholar 

  • [CD80] Chazelle, B. M., Dobkin, D. P., Detection is easier than computation,Proc. 12th Annual ACM Symposium on the Theory of Computing (1980), pp. 146–153.

  • [CE88] Chazelle, B. M., Edelsbrunner, H., An optimal algorithm for intersecting line segments in the plane,29th Annual Symposium on Foundations of Computer Science, October 1988, pp. 590–600.

  • [CL71] Chakerian, G. D., Lange, L. H., Geometric extremum problems,Mathematics Magazine, vol. 44 (1971), pp. 57–69.

    Google Scholar 

  • [CL85] Ching, Y. T., Lee, D. T., Finding the diameter of a set of lines,Pattern Recognition, vol. 18 (1985), pp. 249–255.

    Google Scholar 

  • [CY84] Chang, J. S., Yap, C. K., A polynomial solution for potato-peeling and other polygon inclusion and enclosure problems,Proc. Foundations of Computer Science, West Palm Beach, Fla. (1984), pp. 408–416.

  • [DA84] DePano, N. A. A., Aggarwal, A., Finding restrictedk-envelopes for convex polygons,Proc. 22nd Allerton Conference, Urbana, Ill. (1984), pp. 81–90.

  • [DK83] Dobkin, D. P., Kirkpatrick, D. G., Fast detection of polyhedral intersection,Theoretical Computer Science, vol. 27 (1983), pp. 241–253.

    Google Scholar 

  • [DT90] Devroye, L., Toussaint, G. T., Convex hulls for random lines, Tech. Rept. SOCS-90.11, School of Computer Science, McGill University, (1990).

  • [Dy84] Dyer, M. E., Linear time algorithms for two-and three-variable linear programs,SIAM Journal of Computing, Vol. 13, No. 1 (1984), pp. 31–45.

    Google Scholar 

  • [Ed85] Edelsbrunner, H., Finding transversals for sets of simple geometric figures,Theoretical Computer Science, vol. 35 (1985), pp. 55–69.

    Google Scholar 

  • [Ed85b] Edelsbrunner, H., Computing the extreme distances between two convex polygons,Journal of Algorithms, vol. 6 (1985), pp. 213–224.

    Google Scholar 

  • [EOW81] Edelsbrunner, H., Overmars, M. H., Wood, D., Graphics in flatland: a case study, Tech. Report F79, Technical University of Graz (1981).

  • [EMPRWW82] Edelsbrunner, H., Maurer, H. A., Preparata, F. P., Rosenberg, A. L., Welzl, E., Wood, D., Stabbing line segments,BIT, vol. 22 (1982), pp. 274–281.

    Google Scholar 

  • [ET85] ElGindy, H., Toussaint, G. T., Efficient algorithms for inserting and deleting edges from triangulations,Proc. Intl. Conf. on foundations of Data Organization, Kyoto, Japan (1985).

  • [Gr58] Grunbaum, B., On common transversals,Arch. Math., vol. 9 (1958), pp. 465–469.

    Google Scholar 

  • [He89] Hershberger, J., Finding the upper envelope ofn line segments inO(nlogn) time,Information Processing Letters, vol 33 (1989), pp. 169–174.

    Google Scholar 

  • [HM88] Houle, M., Maciel, A., Finding the widest empty corridor through a set of points, inSnapshots of Computational and Discrete Geometry, G. T. Toussaint, ed., Tech. Report SOCS-88.11, Computational Geometry Laboratory, McGill University (1988), pp. 201–214.

  • [Ho88] Houle, M., A measure of separability for point sets, inSnapshots of Computational and Discrete Geometry, G. T. Toussaint, ed., Tech. Report SOCS-88.11, Computational Geometry Laboratory, McGill University (1988), pp. 21–36.

  • [HV49] Horn, A., Valentine, F. A., Some properties ofL-sets in the plane,Duke Mathematics Journal, vol. 16 (1949), pp. 131–140.

    Google Scholar 

  • [Ka61] Kazarinoff, N. D.,Geometric Inequalities, Published by the Mathematical Association of America (1961).

  • [Ke88] Ke, Y., Detecting the weak visibility of a simple polygon and related problems, The Johns Hopkins University, manuscript (1988).

  • [KS86] Kirkpatrick, D. G., Seidel, R., The ultimate planar convex hull algorithm?SIAM Journal on Computing, vol. 15, No. 1 (1986), pp. 287–299.

    Google Scholar 

  • [KL85] Klee, V., Laskowski, M. C., Finding the smallest triangles containing a given convex polygon,Journal of Algorithms, vol. 6 (1985), pp. 359–375.

    Google Scholar 

  • [La59] Lange, L. H., Cutting certain minimal corners,Mathematics Magazine, vol. 32 (1959), pp. 157–160.

    Google Scholar 

  • [Le80] Lewis, T., Two counterexamples concerning transversals for convex subsets of the plane,Geometriae Dedicata, vol. 9 (1980), pp. 461–465.

    Google Scholar 

  • [Me83] Megiddo, N., Linear-time algorithms for linear programming inR 3 and related problems,SIAM Journal on Computing, Vol. 12 (1983), pp. 759–776.

    Google Scholar 

  • [Ni81] Niven, I.,Maxima and Minima Without Calculus, Published by the Mathematical Association of America (1981).

  • [OAMB86] O'Rourke, J., Aggarwal, A., Maddila, S., Baldwin, M., An optimal algorithm for finding minimal enclosing triangles,Journal of Algorithms, vol. 7 (1986), pp. 258–269.

    Google Scholar 

  • [O'R87] O'Rourke, J.,Art Gallery Theorems and Algorithms, Oxford University Press (1987).

  • [O'R81] O'Rourke, J., An on-line algorithm for fitting straight lines between data ranges,Communications of the ACM, vol. 24, No. 9 (1981), pp. 574–578.

    Google Scholar 

  • [OV81] Overmars, M., van Leeuwen, H., Mamtenance of configurations in the plane,Journal of Computer & System Sciences, vol. 23 (1981), pp. 166–204.

    Google Scholar 

  • [Ro88] Robert, J.-M., Stabbing hyperspheres by a hyperplane, inSnapshots of Computational and Discrete Geometry, G. T. Toussaint, ed., Tech. Rep. SOCS-88.11, Computational Geometry Lab., McGill University (1988), pp. 181–188.

  • [Ro85] Rohnert, H., Shortest paths in the plane with convex polygonal obstacles, Tech. Rept. A85/06, University of Saarbrucken (1985).

  • [SH76] Shamos, M. I., Hoey, D., Geometric intersection problems,Seventeenth Annual IEEE Symposium on the Foundations of Computer Science (1976), pp. 208–215.

  • [Sha89] Sharir, M., The shortest watchtower and related problems for polyhedral terrains,Information Processing Letters (in press).

  • [SS86] Sack, J.-R., Suri, S., An optimal algorithm for detecting weak visibility of a polygon, Tech. Rept. SCS-TR-114, Carleton University, Ottawa (1986).

    Google Scholar 

  • [ST88] Shermer, T., Toussaint, G. T., Characterizations of convex and star-shaped polygons, inSnapshots of Computational and Discrete Geometry, G. Toussaint, ed. Rept. SOCS-88.11, School of Computer Science, McGill Univ. (1988).

  • [Te88] Teichman, M., Shoving a table into a corner, inSnapshots of Computational and Discrete Geometry, G. T. Toussaint, ed., Tech. Report SOCS-88.11, Computational Geometry Laboratory, McGill University (1988), pp. 99–118.

  • [To83] Toussaint, G. T., Solving geometric problems with the rotating calipers,Proc. MELECON' 83, Athens, Greece (1983).

  • [Va53] Valentine, F. A., Minimal sets of visibility,Proc. American Mathematical Society, vol. 4 (1953), pp. 917–921.

    Google Scholar 

  • [Va70] Valentine, F. A., Visible shorelines,American Mathematical Monthly, vol. 77 (1970), pp. 146–152.

    Google Scholar 

  • [Wa76] Wagner, N. R., The sofa problem,American Mathematical Monthly, vol. 83 (1976), pp. 188–189.

    Google Scholar 

  • [We88] Wenger, R., Stabbing and separation, Ph. D. thesis, School of Computer Science, McGill University (1988).

Download references

Author information

Authors and Affiliations

  1. School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada

    B. Bhattacharya

  2. School of Computer Science, McGill University, Montreal, P.Q., Canada

    G. Toussaint

Authors
  1. B. Bhattacharya
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. G. Toussaint
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bhattacharya, B., Toussaint, G. Computing shortest transversals. Computing 46, 93–119 (1991). https://doi.org/10.1007/BF02239165

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02239165

AMS Subject Classifications

Key words

Search

Navigation