Suppose you generate random chords of a circle, with endpoints selected uniformly over the circumference, rejecting any chord that crosses a previously generated chord.
The disk is then partitioned into regions bounded by chords alternating with circular arcs.
For example, here are $n{=}100$ random noncrossing chords, with a region bounded by 5 chords highlighted
(in green).
I am interested in the statistics of the structure of the dual trees for these regions.
Assign each region a node,
and connect two nodes by an edge if they share a chord. In the example above, the highlighted
region's node has degree 5.
Example questions: What is the expected maximum degree of a node for $n$ chords?
Making a max-degree node the root, what is the expected height of the tree?
(In the example above, the height is 21.)
Etc.
Has anyone encountered this model before?
Or a model sufficiently analogous to help establish these statistics?
Thanks for any pointers!
Edit. Many thanks for the wealth of information provided by the community!
I have not yet absorbed all the information in the cited papers,
but so far I have not found this specific question answered (although it is likely implied, perhaps
in the papers they cite):
What is the expected maximum degree of a node as $n rightarrow infty$? What brought me to this
topic in the first place is that I wondered if it might be near 3.
No comments:
Post a Comment