Background: In the age of social media and big data, privacy concerns are a growing issue as individuals worry about the misuse of their sensitive information. Differential privacy is considered the gold standard for privacy protection in data analysis, as it provides a mathematical guarantee that an individual will not be significantly affected when their sensitive data is used for data analysis. The task of extracting useful information about a group of people without revealing meaningful details about individuals can be described by the private interior point problem, which involves finding a point inside a convex hull using a differentially private algorithm.

Goals: Since data can be represented by more than just points, this thesis aims to extend the definition of the private interior point problem by redefining it as finding a point inside the union of given squares using a differentially private algorithm.

Methods: To achieve this, we will develop and analyze two differential private algorithms that address two variations of this problem. The first allows only axis- aligned squares as input (ASPIP), while the second imposes no restrictions on the input squares (SPIP).

Results: The experiments show that both algorithms perform well in solving their respective variation of this problem. Furthermore, the analysis reveals that a good bound on the input size can be established if a certain overlap of input squares is known beforehand, ensuring that the constraints of differential privacy are still met.

Conclusion: Both algorithms provide a good initial step towards better understanding this version of the private interior point problem by offering useful bounds on input size, as well as acceptable execution time and space usage. However, there is still future work that needs to be addressed, such as generalizing this problem to higher dimensions.