Determining Sample Spaces for Sylvester’s Four Point Problem

I don’t have any background in geometric probability, so may I ask for forgiveness if the following is wrong or doesn’t make sense:

Assumptions:

  • no three sampled points are collinear
  • the (naive) geometric probability in euclidean space is equal to the ratio of lengths or areas
  • the probabilites do not change under isometric transformations and/or uniform scaling
  • the probability of a set $ P4:=\lbrace p_1,\ p_2,\ p_3,\ p_4\rbrace$ of four points being in convex configuration in the euclidean plane is independent of the order in which the elements are drawn by the sampling process; that in turn means that we assume that
  • $ \lbrace p_1,\ p_2,\ p_3\rbrace$ resembles the corners of $ T_{max}$ , the triangle of largest area
  • $ \lbrace p_1,\ p_2,\ p_3\rbrace$ have been drawn uniformly from the boundary of their circumcircle, which has implications on the probability of encountering $ T_{max}$ with specific values for the pair of smallest central angles.
  • the smallest circle enclosing $ P4$ is the unit circle centered at the origin
  • the longest side of $ T_{max}$ is bisected by the non-negative part of the x-axis

Under the above assumptions the probability of encountering a convex quadrilateral equals the blue area divided by the blue plus red area in the images below:

probability of 4 four points in convex configuration if the largest triangle is acute

the sampling area in case of acute $ T_{max}$ equals the entire unit disk

probability of four points in convex configuration if the largest triangle is obtuse

the sampling area in case of acute $ T_{max}$ equals the unit disk with a notch

The notch in the case of obtuse $ T_{max}$ is owed to the assumption that the first three points resemble $ T_{max}$ which implies that points outside $ T_{max}$ that generate a deltoid configuration would contradict the maximality of the area of $ T_{max}$

If the above makes sense, then the probability of four points being in convex configuration could be calculated by integrating over the ratios of the blue areas over the entire sampling area as defined by the $ T_{max}$ multiplied with the probability of $ T_{max}$ as a consequence of uniform sampling on the boundary of the unit circle.

Questions:

  • have similar ways of defining the sample spaces for Sylvester’s Four Point Problem already been described or investigated?
  • what are objections against the proposed against the proposed definition of the available sample space on basis of $ T_{max}$ ?

Remark:

in case of obtuse $ T_{max}$ the area of the sample space can be calculated on basis of angles $ \alpha$ and $ \beta$ that are adjacent to the longest side of $ T_{max}$ as follows, keeping in mind that that longest edge is the diameter of the unit circle:

  • the area of the lower blue half-disk equals $ \ \frac{\pi}{2}\ $
  • the area $ \ A_{\alpha}\ $ of the union of $ \ T_{max}\ $ with the blue region opposite to angle $ \ \alpha$ equals $ \ \alpha+\sin(\alpha)cos(\alpha)\ $ and analogous $ \ A_{\beta}\ $ for angle $ \ \beta\ $
  • the area of $ \ A_{T_{max}}\ $ of $ \ T_{max}\ $ equals $ \ \frac{1}{\cot(\alpha)+\cot(\beta)}\ $

The area of the sampling area for obtuse $ \ T_{max}\ $ then equals $ \ \frac{\pi}{2}+A_{\alpha}+A_{\beta}-A_{T_{max}}$

What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not

Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not.

For example, consider the following two trees:

trees

Example trees T and U are isomorphic.
An isomorphism (bijection) is described in the table below:

  T          U   1          2   2          4   3          1   4          5   5          3   "white"    "green"   "blue"     "white"      

Below are some things to know about the problem:

  • Nodes are colored
  • edges are not colored.
  • Nodes are free to be any color. Adjacent nodes are allowed to be the same color.
  • which node is the root node of each tree cannot be changed.
  • children are un-ordered.
  • the tree is not necessarily a binary tree. a node could have 3 children, 4 children, 5, etc…

Formally, a colored tree is a tuple (VS, ES, root, color_set, color_map) such that:

  • VS is the vertex set
  • ES is the edge set
  • (VS, ES) is a undirected tree
  • root is a element of VS
  • color_set is a set of objects called “colors”
  • color_map is a mapping from VS to color_set
  • every element of color_set appears in the range of color_map at least once. That is, every color is applied to at least one node.

colored trees T and U are isomorphic if and only if there exists a bijection, PHI from the vertex set of T, VT, to the vertex set of U, VU such that:

  • the root of one tree is matched to the root of the other tree
  • for all nodes v, w in VT, {v, w} is an edge in tree T if and only if {PHI(v), PHI(w)} is an edge in tree U
  • for all nodes v, w in VT, v and w are the same color in tree T if and only if PHI(v), PHI(w) are the same color in tree U

Determining the DP subproblem given a problem

I’m reviewing DP and I was wondering the intuition behind determining the subproblems for some DP problems.

For example, consider 2 similar problems.

Given a set of 1, 2, and 3 steps you can take, find the total number of ways to reach X steps.

Given a set of 1, 2, 3 coins, find the total number of ways to reach X amount.

After doing both problems, I’ve found that the main difference in the problems is that for coins, order does not matter. If you have 1 coin and 3 coin, it’s the same as if you have a 3 coin and 1 coin. With steps, order matters. Taking 1 step then 3 step is different than taking 3 step then 1 step.

With that, the correct subproblem it seems for the coins is given 1 coin, how many ways can we reach X amount. Thus you build out your solution first with 1 coin, then add a coin, and then add a coin.

With the stairs problem, it seems like the subproblem is given a set of stairs with just 1 step, how many ways can we climb up. Then do it for 2 steps, and so on until you reach X.

I’m wondering if there’s some intuition behind how to choose these subproblems. It seems like just as easily, you could say for the stairs problem the subproblem can be given the ability to take 1 step only, how many ways are there to climb up X steps. Now add the ability to take 2 steps, and so on.

Any tips to think through these problems would be greatly appreciated!

Is Overchanneling announced before or after determining if a spell hits? [duplicate]

This question already has an answer here:

  • When must the wizard choose to overchannel? 4 answers

School of Evocation Wizards in 5E gain Overchannel at level 14. It states:

When you cast a wizard spell 1st through 5th level that deals damage, you can deal maximum damage with that spell. The first time you do so, you suffer no adverse effect.

If you use the feature again it gets progressively worse.


Do you have to announce that you are using Overchannel before or after determining if a spell hits or the target fails their save?

Something like: First, declare “I’m Overchanneling Chromatic Orb” (or hopefully something more flavorful)… Then, if it hits, it deals max damage but if it misses the Overchannel is wasted.

Alternatively, can you wait to see if the Chromatic Orb hits and then say, “Seeing its effectiveness I channel all of my energy to enhance it — Overchanneling” (or again some other flavorful speech)

NGINX: determining what port a request forwarded by an AWS load balancer was originally sent to

I want a set-up where an Amazon load balancer forwards requests received on any of port 21001, 21002 and 21003 and send them all to an NGINX reverse-proxy on port 443 (regardless) which in turn forwards the request to a member of a cluster by IP address. Is there a directive I can include in an nginx.conf to determine the port that the original request was sent to in order to route this? X-Forwarded-Proto seems close, but only determines between https and http, not arbitrary high TCP ports.

Determining Saving Throw Values

So this may be a newbie question but I am currently DMing a 5e home campaign, and I was looking at the Drow monster stat block. They have innate spellcasting abilities and one of those is Faerie Fire. In the description it states that the targets must make a DEX saving throw or be outlined in color. Now my question is, how do I determine the number that is needed to PASS the dex saving throw as it is not stated and I am just a bit confused as to how to arrive at this number. Thank you guys so much!

Determining the entropy of a string if each character has a slight bias

Let’s say I need to generate a 32-character secret comprised of ASCII characters from the set ‘0’..’9′. Here’s one way of doing it:

VALID_CHARS = '0123456789'  generate_secret_string() {     random = get_crypto_random_bytes(32)     secret = ''     for (i = 0; i < 32; i++) {         secret += VALID_CHARS[random[i] % 10]     }     return secret } 

My concern is that my character selection is biased. Because 10 doesn’t divide evenly into 256, the first 6 VALID_CHARS are slightly more likely to occur.

The secret space is 1032, but my generated secrets have less entropy than that. How can I calculate precisely how much entropy I actually have?

Dealing with test condition ‘=’ for a while loop when determining a bound function/loop variant

The following is the definition of what a bound function for a while loop must satisfy:

1.an integer-valued, total function of some of the inputs, variables and global data that are defined when the loop is reached.

2.When the loop body is executed, the value of this function is decreased by at least one before the loop’s test is checked again, if at all.

3.If the value of this function is ≤ 0 and the loop’s test is checked then the test fails (ending this execution of the loop).

Given a while loop as such,

While (j<= n) {.....; j++} 

I am trying to find a bound function/loop variant for this simple while loop.

n-j is not a loop function since point (3) would fail. and n-j-1 is not a loop function since the loop would not run initially if n=j (since n-j-1=-1>=f(i,n)), and I am not sure if the latter is a total function due to the presence of a ‘-1’.

How do I deal with the ‘=’ in the ‘<=’ to determine a bound function that satisfies the while loop?