Generate Random Point in a Circle

Problem Description

Given the radius and the position of the center of a circle, implement the function randPoint which generates a uniform random point inside the circle. A point on the circumference of the circle is considered to be in the circle.

Key Insights

• To generate a random point uniformly within a circle, we can use polar coordinates.
• The angle can be chosen randomly from 0 to 2π (full circle).
• The radius must be chosen such that the area is uniformly distributed, which involves taking the square root of a uniform random number multiplied by the radius.
• The final point can be computed using trigonometric functions based on the chosen angle and calculated radius.

Space and Time Complexity

Time Complexity: O(1) - Each call to randPoint performs a constant amount of work. Space Complexity: O(1) - We only use a fixed amount of extra space for calculations.

Solution

The solution utilizes random number generation and polar coordinates to ensure uniform distribution of points within the circle. The algorithm involves:

1. Generating a random angle from 0 to 2π.
2. Generating a random radius that scales with the area of the circle, specifically using the square root of a uniformly distributed random number multiplied by the radius.
3. Converting polar coordinates (radius, angle) to Cartesian coordinates (x, y) using the equations:
   • x = x_center + radius * cos(angle)
   • y = y_center + radius * sin(angle)

Code Solutions