This paper explores the application of random sampling in computational geometry, focusing on several new geometric algorithms. The algorithms are "Las Vegas" types, meaning their expected bounds are based on the random behavior of the algorithms. Key results include: 1. **Line Segment Intersections**: An algorithm is presented to report all intersecting pairs of a set of line segments in the plane, requiring $O(A + n \log n)$ expected time, where $A$ is the number of intersecting pairs and $n$ is the number of segments. The algorithm requires $O(n)$ space in the worst case. 2. **Convex Hulls**: An algorithm is given to compute the convex hull of a set of points in $E^3$ in $O(n \log A)$ expected time, where $n$ is the number of points and $A$ is the number of points on the hull surface. 3. **Triangulation of Simple Polygons**: A simple Las Vegas algorithm is provided to triangulate a simple polygon in $O(n \log \log n)$ expected time. 4. **Halfspace Range Reporting**: Improved bounds are given for halfspace range reporting, with algorithms requiring $O(n)$ storage, $O(n \log n)$ expected preprocessing time, and query times of $O(A + n^{1 + \epsilon - \gamma})$ for $\gamma = 1 / (1 + (d - 1) / [d/2])$. 5. **Combinatorial Quantity**: The paper also provides asymptotically tight bounds for a combinatorial quantity related to halfspace partitions of point sets, showing that the number of $(\leq k)$-sets of a set of $n$ points in $E^d$ is $O(n^{[d/2]} k^{[d/2]})$ as $n/k \to \infty$. The paper uses a formal framework to abstract geometric computations, allowing for the application of random sampling techniques to a variety of geometric structures. The main theorem, which bounds the average work done for a member of a set of regions defined by a random subset, is a key tool in proving these results.This paper explores the application of random sampling in computational geometry, focusing on several new geometric algorithms. The algorithms are "Las Vegas" types, meaning their expected bounds are based on the random behavior of the algorithms. Key results include: 1. **Line Segment Intersections**: An algorithm is presented to report all intersecting pairs of a set of line segments in the plane, requiring $O(A + n \log n)$ expected time, where $A$ is the number of intersecting pairs and $n$ is the number of segments. The algorithm requires $O(n)$ space in the worst case. 2. **Convex Hulls**: An algorithm is given to compute the convex hull of a set of points in $E^3$ in $O(n \log A)$ expected time, where $n$ is the number of points and $A$ is the number of points on the hull surface. 3. **Triangulation of Simple Polygons**: A simple Las Vegas algorithm is provided to triangulate a simple polygon in $O(n \log \log n)$ expected time. 4. **Halfspace Range Reporting**: Improved bounds are given for halfspace range reporting, with algorithms requiring $O(n)$ storage, $O(n \log n)$ expected preprocessing time, and query times of $O(A + n^{1 + \epsilon - \gamma})$ for $\gamma = 1 / (1 + (d - 1) / [d/2])$. 5. **Combinatorial Quantity**: The paper also provides asymptotically tight bounds for a combinatorial quantity related to halfspace partitions of point sets, showing that the number of $(\leq k)$-sets of a set of $n$ points in $E^d$ is $O(n^{[d/2]} k^{[d/2]})$ as $n/k \to \infty$. The paper uses a formal framework to abstract geometric computations, allowing for the application of random sampling techniques to a variety of geometric structures. The main theorem, which bounds the average work done for a member of a set of regions defined by a random subset, is a key tool in proving these results.