This paper presents several new geometric algorithms that use random sampling. The algorithms are "Las Vegas" and have expected bounds based on the random behavior of the algorithms. One algorithm reports all intersecting pairs of line segments in the plane in O(A + n log n) expected time, where A is the number of intersecting pairs. Another algorithm computes the convex hull of a point set in E³ in O(n log A) expected time, where A is the number of points on the surface of the hull. A simple Las Vegas algorithm triangulates simple polygons in O(n log log n) expected time. Algorithms for half-space range reporting are also given. The paper also provides asymptotically tight bounds for a combinatorial quantity related to half-space partitions of point sets. The paper discusses the use of random sampling in computational geometry, particularly for divide-and-conquer problems. It presents algorithms for line segment intersections, convex hulls, and triangulation of simple polygons. The algorithms use random sampling to reduce the size of subproblems, leading to improved bounds for certain randomized algorithms and a combinatorial quantity. The paper also provides improved bounds for half-space range reporting, showing that a new algorithm requires expected O(n^{floor(d/2)+ε}) preprocessing time and O(n^{floor(d/2)+ε}) storage. The query time is O(A + log n), where A is the size of the answer to the query. The paper also discusses the concept of k-sets and provides tight bounds for the number of k-sets. It shows that the number of k-sets is Θ(n^{floor(d/2)}k^{ceil(d/2)}), as n/k → ∞, for fixed d. The paper also provides a formal framework for geometric computations and applies it to various geometric structures. The paper presents a theorem that gives a bound on the quantity g_{k,d}(n), which is the maximum number of k-sets over all n-point sets in E^d. The paper also discusses the use of random sampling in algorithms for half-space range queries, showing that a new algorithm requires less storage and preprocessing at the cost of a longer query time. The paper concludes with a theorem that shows that the vertical visibility map of a set of line segments can be computed in O(A + n log n) expected time and O(n) space. The paper also discusses the triangulation of simple polygons, showing that it can be done in O(n log log n) expected time.This paper presents several new geometric algorithms that use random sampling. The algorithms are "Las Vegas" and have expected bounds based on the random behavior of the algorithms. One algorithm reports all intersecting pairs of line segments in the plane in O(A + n log n) expected time, where A is the number of intersecting pairs. Another algorithm computes the convex hull of a point set in E³ in O(n log A) expected time, where A is the number of points on the surface of the hull. A simple Las Vegas algorithm triangulates simple polygons in O(n log log n) expected time. Algorithms for half-space range reporting are also given. The paper also provides asymptotically tight bounds for a combinatorial quantity related to half-space partitions of point sets. The paper discusses the use of random sampling in computational geometry, particularly for divide-and-conquer problems. It presents algorithms for line segment intersections, convex hulls, and triangulation of simple polygons. The algorithms use random sampling to reduce the size of subproblems, leading to improved bounds for certain randomized algorithms and a combinatorial quantity. The paper also provides improved bounds for half-space range reporting, showing that a new algorithm requires expected O(n^{floor(d/2)+ε}) preprocessing time and O(n^{floor(d/2)+ε}) storage. The query time is O(A + log n), where A is the size of the answer to the query. The paper also discusses the concept of k-sets and provides tight bounds for the number of k-sets. It shows that the number of k-sets is Θ(n^{floor(d/2)}k^{ceil(d/2)}), as n/k → ∞, for fixed d. The paper also provides a formal framework for geometric computations and applies it to various geometric structures. The paper presents a theorem that gives a bound on the quantity g_{k,d}(n), which is the maximum number of k-sets over all n-point sets in E^d. The paper also discusses the use of random sampling in algorithms for half-space range queries, showing that a new algorithm requires less storage and preprocessing at the cost of a longer query time. The paper concludes with a theorem that shows that the vertical visibility map of a set of line segments can be computed in O(A + n log n) expected time and O(n) space. The paper also discusses the triangulation of simple polygons, showing that it can be done in O(n log log n) expected time.