research-article

A linear algorithm for computing convex hulls for random lines

Authors:

Daniel Berend,

Vladimir BravermanAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 5, Issue 4

Article No.: 42, Pages 1 - 21

https://doi.org/10.1145/1597036.1597046

Published: 06 November 2009 Publication History

Get Access

Abstract

Finding the convex hull of n points in the plane requires O(n log n) time in general. In Devroye and Toussaint [1993] and Golin et al. [2002] the problem of computing the convex hull of the intersection points of n lines was considered, where the lines are chosen randomly according to two various models. In both models, linear-time algorithms were developed. Here we improve the results of Devroye and Toussaint [1993] by giving a universal algorithm for a wider range of distributions.

References

[1]

Atallah, M. 1986. Computing the convex hull of line intersections. J. Algor. 7, 285--288.

Digital Library

Google Scholar

[2]

Berend, D. and Braverman, V. 2005. Convex hull for intersections of random lines. In Proceedings of the International Conference on the Analysis of Algorithms 25, 11--12.

Google Scholar

[3]

Chan, T. 1996. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete Comput. Geom. 16, 361--368.

Digital Library

Google Scholar

[4]

Ching, Y. and Lee, D. 1985. Finding the diameter of a set of lines. Pattern Recogn. 18, 249--255.

Crossref

Google Scholar

[5]

Cormen, T., Leiserson, G., and Rivest, R. 2000. Introduction to Algorithms. The MIT Press.

Digital Library

Google Scholar

[6]

Devroye, L. and Toussaint, G. 1993. Convex hulls for random lines. J. Algor. 14, 381--394.

Digital Library

Google Scholar

[7]

Golin, M., Langerman, S., and Steiger, W. 2002. The convex hull for random lines in the plane. In Proceedings of the Japan Conference on Discrete and Computational Geometry (JCDCG'02).

Google Scholar

[8]

Graham, R. 1972. An efficient algorithm for determining the convex hull of a finite planar set. Inf. Process. Lett. 1, 132--133.

Crossref

Google Scholar

[9]

Jarvis, R. 1973. On the identification of the convex hull of a finite set of points in the plane. Inf. Process. Lett. 2, 18--21.

Crossref

Google Scholar

[10]

Kirkpatrick, D. and Seidel, R. 1986. The ultimate planar convex hull algorithm? SIAM J. Comput. 15, 287--299.

Digital Library

Google Scholar

[11]

Melkman, A. 1987. On-line construction of the convex hull of a simple polyline. Inf. Process. Lett. 25, 11--12.

Digital Library

Google Scholar

[12]

Preparata, F. and Shamos, M. 1986. Computational Geometry: An Introduction. Springer-Verlag, New-York.

Digital Library

Google Scholar

Index Terms

A linear algorithm for computing convex hulls for random lines
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Convex hulls of spheres and convex hulls of disjoint convex polytopes

Given a set @S of spheres in E^d, with d>=3 and d odd, having a constant number of m distinct radii @r"1,@r"2,...,@r"m, we show that the worst-case combinatorial complexity of the convex hull of @S is @Q(@__ __"1"=<"i"<>"j"=<"mn"in"j^@__ __^d^2^@__ __), ...
Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

Given a set Σ of spheres in E^d, with d≥3 and d odd, having a fixed number of m distinct radii ρ₁,ρ₂,...,ρ_m, we show that the worst-case combinatorial complexity of the convex hull CH_d(Σ) of Σ is Θ(Σ_{{1≤i≠j≤m}}n_in_j^{⌊ d/2 ⌋}), where n_i is the number of ...
Robust algorithms for constructing strongly convex hulls in parallel

Given a set S of n points in the plane, an ε-strongly convex δ-hull of S is defined as a convex polygon P with the vertices taken from S such that no point of S lies farther than δ outside P and such that even if the vertices of P are perturbed by as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 5, Issue 4

October 2009

281 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1597036

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2009

Accepted: 01 May 2009

Revised: 01 February 2009

Received: 01 August 2005

Published in TALG Volume 5, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
348
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)2

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Index Terms

Recommendations

Convex hulls of spheres and convex hulls of disjoint convex polytopes

Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes

Robust algorithms for constructing strongly convex hulls in parallel