2
$\begingroup$

  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.

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

1 Answer 1

Reset to default
1
$\begingroup$

You might enjoy learning about dynamic programming: https://cs.stackexchange.com/tags/dynamic-programming/info

Improve this answer
$\endgroup$
5
  • $\begingroup$ Sure, I will check it out. But, has anything been done before related to the problem I mentioned in the question ? I just want some intuition and guidance from a pre-existing literature, but no amount of Google search have me relevant results. $\endgroup$
    – The Limit Does Not Exist
    Mar 15, 2022 at 2:05
  • 2
    $\begingroup$ @TheLimitDoesNotExist, that's the thing about research! Research typically involves trying to tackle some problem where no one knows how to solve it -- where you can't solve it by Google search or hoping someone else has already figured out a good solution -- where it's not even clear whether a good solution will be possible. That's the joy and the challenge, and even if I knew of some pre-existing literature (which I don't), I wouldn't want to deprive you of the opportunity to experience that for yourself. $\endgroup$
    – D.W. ♦
    Mar 15, 2022 at 3:56
  • $\begingroup$ @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. $\endgroup$
    – greybeard
    Mar 21, 2022 at 8:23
  • $\begingroup$ @greybeard I get your point. But I'm absolutely new to all this. Could you suggest any keywords to search, like the one mentioned in one of the earlier comments, "bichromatic point sets"? I just want something to give me direction, and obviously a research problem is not like some back of the book exercise, which would already have answers. $\endgroup$
    – The Limit Does Not Exist
    Apr 5, 2022 at 4:16
  • $\begingroup$ @TheLimitDoesNotExist, in my experience, research is not limited to "finding someone else who previously thought about and solved this problem". Research often involves working on a problem and being the first to solve it (or, the first to figure out how to solve it and also explain the solution in the published literature). It sounds like you have the impression that research is limited to searching previously written texts to find where someone else discussed the same problem, but that's not how research works in practice -- research is more than that. $\endgroup$
    – D.W. ♦
    Apr 5, 2022 at 4:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.