RandPoint in a Circle

Problem Description

Given the radius and center of a circle, implement a function to generate a uniform random point inside the circle. The Solution class has:

• Solution(double radius, double x_center, double y_center): Initializes the object with the circle's radius and center coordinates.
• randPoint(): Returns a random point [x, y] inside the circle. A point on the circumference is considered inside.

Constraints:

• 0 < radius <= 10^8
• -10^7 <= x_center, y_center <= 10^7
• Maximum of 3 * 10^4 calls to randPoint()

Example:

Input:
["Solution", "randPoint", "randPoint", "randPoint"]
[[1.0, 0.0, 0.0], [], [], []]
Output:
[null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]

Brute Force Approach

A simple, albeit inefficient, approach involves generating random points within a square that encloses the circle and then checking if the generated point falls within the circle. This process is repeated until a valid point is found.

1. Generate random x and y coordinates within the square's bounds.
2. Check if the point lies within the circle using the distance formula.
3. If the point is inside the circle, return it; otherwise, repeat steps 1 and 2.

Code (Illustrative - Not Optimal)

import java.util.Random;

class Solution {
    private double radius, x_center, y_center;
    private Random random;

    public Solution(double radius, double x_center, double y_center) {
        this.radius = radius;
        this.x_center = x_center;
        this.y_center = y_center;
        this.random = new Random();
    }

    public double[] randPoint() {
        while (true) {
            double x = x_center + (random.nextDouble() * 2 - 1) * radius;
            double y = y_center + (random.nextDouble() * 2 - 1) * radius;
            if (Math.pow(x - x_center, 2) + Math.pow(y - y_center, 2) <= Math.pow(radius, 2)) {
                return new double[]{x, y};
            }
        }
    }
}

Time Complexity

The time complexity is, on average, O(1) since the number of tries is expected to be constant. However, in the worst case, it could be O(infinity) if the random number generator keeps producing points outside the circle.

Space Complexity

The space complexity is O(1), as we only use a constant amount of extra space.

Optimal Approach

To generate a uniform random point inside the circle, it's essential to avoid bias. Generating random points within a square and rejecting those outside the circle, as shown in the brute-force method, can lead to uneven distribution, especially near the circle's edges.

A better approach involves generating a random radius and a random angle:

1. Generate a random radius r such that 0 <= r <= radius and a random angle theta such that 0 <= theta < 2*PI.
2. Convert polar coordinates (r, theta) to Cartesian coordinates (x, y).
   • x = x_center + r * cos(theta)
   • y = y_center + r * sin(theta)
3. Return the point [x, y]

However, generating r uniformly between 0 and radius will result in a non-uniform distribution of points within the circle, concentrating points near the center. To correct this, generate r such that r = radius * sqrt(random()). This ensures a uniform distribution.

Code (Optimal)

import java.util.Random;

class Solution {
    private double radius, x_center, y_center;
    private Random random;

    public Solution(double radius, double x_center, double y_center) {
        this.radius = radius;
        this.x_center = x_center;
        this.y_center = y_center;
        this.random = new Random();
    }

    public double[] randPoint() {
        double r = radius * Math.sqrt(random.nextDouble());
        double theta = random.nextDouble() * 2 * Math.PI;
        double x = x_center + r * Math.cos(theta);
        double y = y_center + r * Math.sin(theta);
        return new double[]{x, y};
    }
}

Time Complexity

The time complexity is O(1) since it involves a fixed number of calculations.

Space Complexity

The space complexity is O(1) because we only use a constant amount of extra space.

Edge Cases

• radius = 0: The problem statement specifies that 0 < radius <= 10^8. If the radius was 0, we would only return the center point.
• Large radius/center values: The constraints specify a range within which the values can lie. Ensure that calculations do not result in overflow, though double provides sufficient range in this case.
• random.nextDouble() returns 0: The sqrt function handles the case where the random value is 0, and the point generated will be the center.