Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Convex hull for inte ...
Conference paper

Convex hull for intersections of random lines

Daniel Berend (1), Vladimir Braverman (2)
(1) Department of Mathematics [Be'er Sheva]
(2) Department of Electrical Engineering [New York]
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2004
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
Proceedings
DOI
10.46298/dmtcs.3364
License
https://about.hal.science/hal-authorisation-v1
Indicators
602
Views
733
Downloads

Convex hull for intersections of random lines

Daniel Berend (1), Vladimir Braverman (2)
(1) Department of Mathematics [Be'er Sheva]
(2) Department of Electrical Engineering [New York]
Abstract
The problem of finding the convex hull of the intersection points of random lines was studied in Devroye and Toussaint, 1993 and Langerman, Golin and Steiger, 2002, and algorithms with expected linear time were found. We improve the previous results of the model in Devroye and Toussaint, 1993 by giving a universal algorithm for a wider range of distributions.
Keywords
  • [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
  • [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC]
  • convex hull
  • random lines
Cited by

Source: OpenCitations

  • Weak convergence of the intersection point process of Poisson hyperplanes

    Annales de l Institut Henri Poincaré Probabilités et Statistiques

    Authors : Anastas Baci, Gilles Bonnet ORCID, Christoph Thäle

    Journal reference : Volume 58, 2022, pp.

    DOI : 10.1214/21-aihp1201
Preview
Loading PDF preview...