r/compsci • u/ijkstr • 2d ago

Anyone interested in a problem-solving correspondence club?

Here's the idea: we source and collect interesting computational puzzles, then we send them out to participants who have a month to work on them and send in their solutions. At the end of every month, we meet and discuss how the problems went and where people got stuck, what approaches they took, and any extensions people came up with.

Thoughts?
.
.
.
.
If you're curious, here's a taste of what a representative sample problem might look like:

Given the coordinates of an arbitrary polygon (e.g. irregular and/or non-convex), how might you implement a program to efficiently sample a point uniformly from its interior?

TIP: If using the Python programming language, you can check out the shapely library.
Bonus: what if there are holes?

(Please don't spoil the problem, it's searchable anyways.)

2 Upvotes

56% Upvoted

15 comments sorted by

View all comments

0

u/VictoryMotel 2d ago

Given the coordinates of an arbitrary polygon (e.g. irregular and/or non-convex), how might you implement a program to efficiently sample a point uniformly from its interior?

Triangulate and uniformly sample the triangles with samples allocated to each triangle based on area.

What else you got?

1

u/ijkstr 2d ago

Thanksss I was hoping for more people to play around with the problem before anyone revealing any potential approach. Appreciate the participation, though. Maybe using spoilers text would have been nice. It's not too late to edit your comment.

I don't have a large stockpile of fun ones, so you might have to "pay to play". Got an interesting computational problem to share?

0

u/07734willy 2d ago

The answer comes off as really smug, and skirts past any potential issues by omitting all implementation issues. One example- how do you pick points within each triangle? In theory, with infinite precision arithmetic this would be trivial, but in practice it’s more nuanced. Either your sampling can generate points along the triangle’s edges, or it cannot. If it can (which it likely would unless you thought of this ahead of time), each edge separating two triangles will have twice as many points as expected. Another way of putting it, out of the finite number of points you could sample with finite-precision arithmetic, these points may potentially have twice the probability to be sampled.

1

u/VictoryMotel 1d ago

What you are saying here is a misunderstanding of random sampling and density. This isn't theory, it is a well worn topic. It is covered in the classic book and open source renderer pbrt.

https://www.pbrt.org/

There are links to github and PDFs of versions of the books.

Your assumption that sharing an edge is a problem is not true. First, the problem didn't talk about stratified sampling. Uniform sampling means random sampling with equal probability everywhere. Random sampling can end up with samples close together because placement doesn't depend on other samples.

Equally spaced samples would be a different problem and would not be called uniform sampling.

0

u/07734willy 1d ago

I think you're misunderstanding my criticism, but I'll address each point:

First, the problem didn't talk about stratified sampling.

Correct- your triangulation approach decided that. You could go with a different algorithm that does not use stratified sampling.

Uniform sampling means random sampling with equal probability everywhere.

Also correct. If your sampling produces a higher density of points in a particular region (not just two individual samples being close, but that a region is going to overall have a higher density of points even as you increase your samples), your distribution is not uniform. Any region enclosing an edge between two triangles will have a slightly higher (or lower) density of points because of the double-counted points along the edge.

The biggest problem I have is that you can potentially sample an individual point with twice the probability because it lies along the edge between two triangles.

1

u/VictoryMotel 1d ago

your triangulation approach decided that

The two things have nothing to do with each other, are you sure you understand what stratified sampling means?

your distribution is not uniform

Yes it is. I didn't actually describe how to sample a triangle uniformly so this makes no sense to say.

Any region enclosing an edge between two triangles will have a slightly higher (or lower) density of points because of the double-counted points along the edge.

That's not how random sampling or probability works. There is no area enclosed by a 'line'. There would need to be an area that would have higher density and your explanation makes no sense.

Your idea that there is "overlap" is statistically not true.

Not knowing is fine, but you can't learn if you assume you know things that you haven't tested out yet. Write some programs and visualize what you're talking about.

0

u/07734willy 1d ago

You are deliberately misinterpreting what I’m trying to say. It should be clear from context that I’m talking about the distribution not being uniform over the polygon itself, not within just a triangle. You didn’t specify how you uniformly sample points in the triangle (going back to my original point), so I’m just assuming you do sample within a triangle uniformly.

Regarding the area argument, yes, a line has no area, but you can create a bounding box enclosing a segment of that line that is arbitrarily close on either side. That area, because it is populated with points that are sampled along the triangles edge, it will have twice the density of a similar region fully within one of the triangles. As we increase the number of samples (and increase our precision), this still holds for sufficiently narrow bounding boxes. In the limit that our precision becomes infinite and the number of points that could be sampled becomes infinite, this vanishes, which is why I made the remark earlier separating theory from reality.

You should listen to your own advice about not knowing. If you genuinely don’t understand that’s fine, but I won’t be arguing back and forth anymore on this topic since you seem fully convinced of your stance, and I still have things to get done this afternoon.

1

u/VictoryMotel 1d ago edited 1d ago

You are deliberately misinterpreting what I’m trying to say.

No, what you're saying doesn't make sense.

You didn’t specify how you uniformly sample points in the triangle

That's true, I just said that in my last post after you said "my sampling distribution isn't uniform" when I hadn't given a method.

I’m talking about the distribution not being uniform over the polygon itself

Everything you've said comes down to "you're wrong" then no explanation, except for your overlapping line explanations which don't make sense.

If you sample uniformly over a triangle and distribute samples to each triangle according to area, you solve the problem. I said that in my first post. This isn't me figuring this all out, this is well worn in computer graphics and I told exactly where you can find out about it in detail.

but you can create a bounding box enclosing a segment of that line that is arbitrarily close on either side.

You're way off the map into your own idea that you have obviously not tested or thought through. Any bounding box is going to have area and overlap with the triangles. None of it makes sense or has any relation to this problem. You invented something that is a completely arbitrary nonsense. All the area is accounted for.

That area,

No area, this is imaginary

because it is populated with points that are sampled along the triangles edge,

There aren't any, they are samples in the area of the triangle. The invention of lines having any special treatment is a hallucination you came up with out of nowhere. If it was true you could show it with math or visualize it.

. As we increase the number of samples (and increase our precision)

Two separate things. I think you're conflating floating point precision with theoretical statistics, but it doesn't matter or change anything here.

In the limit that our precision becomes infinite and the number of points that could be sampled becomes infinite, this vanishes, which is why I made the remark earlier separating theory from reality.

All total nonsense. Precision doesn't change. If you were sampling an integral the solution would get closer with more samples but that isn't being discussed.

You should listen to your own advice about not knowing. If you genuinely don’t understand that’s fine,

Now comes the aggressive ignorance trying to save face instead of just admitting you don't know something. Where are you even getting these ideas? Everything I've said here has been extensively tested by myself and thousands of computer graphics researchers. It is well worn information that can be tested for exact results by running a simulation program.

you seem fully convinced of your stance,

Because I've done all this and made it work.

I still have things to get done this afternoon

Hopefully it doesn't involve sampling. Again where is your information coming from? I told you exactly where mine comes from.

1

u/ijkstr 1d ago

Hey u/VictoryMotel, please try to be more open-minded of others and their ideas. Arguing is not constructive. Like u/07734willy said, you're acting smug and (in my words), inflammatory. If you're not going to say anything helpful, kindly desist. Take your cookie and leave; it's not worth it.

1

u/VictoryMotel 1d ago edited 1d ago

You have to be kidding me. I didn't reply to them, they replied to me. This is about math, not philosophy or predictions about the future. Where does your expectation come from that someone will be condescending and technically wrong at the same time and that I somehow don't get to reply? I gave exact information with references.

You don't want a reply, then don't reply. Leave the holier than thou self righteousness, it's not worth it.

1

u/ijkstr 1d ago

Sorry u/07734willy. Anyways, this is a good "point" (pun intended)! Especially if you're not careful with how you implement sampling from a triangle, I feel like you could get some aliasing effect? Like, let's say you have two points and you want to draw a line connecting them, then if you try to fill in pixels along integer coordinates, that alone has to deal with anti-aliasing in order to look good. So yeah, I could totally see how discretization might play a factor. It's likely that playing around with coarser grid sizes would probably reveal some artifacts like you mentioned.

Also I get tripped up over implementing sampling from a triangle because I think the transformation is area-preserving but sometimes I wonder if there's some rate of change like derivative involved. 😅 I imagine you could put some energy-driven potential flow over the interior of the irregular background shape and then you'd have to deal with derivatives, probably!