# Research project problem on Computational Geometry

1. (Most fair region) Let $$P$$ be a set of $$n$$ points in the two-dimensional plane. Each point in $$P$$ is either colored red or blue. Given an axis-aligned rectangle $$R_{ab}$$ of size $$a\times b$$ , design a fast algorithm to decide where to place $$R_{ab}$$ in the plane so that the absolute difference between the number of red points and the number of blue points lying inside $$R_{ab}$$ is minimized. As a motivating example, think of each point in $$P$$ as the geographical location of each person. The color of each person could be assigned based on either gender, or political affiliation, or native/non-native speaker, favourite hero etc. We look at the simple setting where there are only two groups/colors. The goal is to detect region(s) which has a fair representation of both groups. Fairness in general is a very popular topic in computer science these days.

2. (Most unfair region) Let $$P$$ be a set of $$n$$ points in the two-dimensional plane. Each point in $$P$$ is either colored red or blue. Given an axis-aligned rectangleRabof size $$a \times b$$, design a fast algorithm to decide where to place $$R_{ab}$$ in the plane so that the absolute difference between the number of red points and the number of blue points lying inside $$R_{ab}$$ is maximized. Following the previous motivating example, this could help detect a region where there is huge gender disparity or detect a region where a particular political party has a strong majority.

These are two related open problems which our course instructor on computational geometry has asked us to work on. Could anyone suggest some literature/resources related to these so that I am able to navigate and appreciate the problem better ? (I haven't been able to find anything related to this on google)

P.S.: I am a 2nd year undergrad student, and this is my first computational geometry course. This "research project problem" is to give us a better flavour of what it takes to be a CS researcher.

• 1. seems trivial without something (like place $R_{ab}$ in $P$'s aaBB ) keeping me from placing $R_{ab}$ where there are no points. Mar 15, 2022 at 14:54
• Lets say you are restricted to place the rectangle where it encloses at least one point. Any ideas as to how to proceed ? Mar 20, 2022 at 6:30
• Possible keywords to search: "bichromatic point sets". Mar 29, 2022 at 3:42

• @TheLimitDoesNotExist: Success in finding information increases with knowledge in the field. no amount of Google search[gave]me relevant results You don't seem to remember the time before: You started by collecting names of Authors as well as publications. For keywords, you needed institutions supporting finding papers that way. The most appreciated publication date was to appear. Mar 21, 2022 at 8:23