Return to Question

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).
alt text http://cs.smith.edu/%7Eorourke/MathOverflow/Chords100.jpg
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.

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! So far I have not found the following 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.

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).
alt text http://cs.smith.edu/%7Eorourke/MathOverflow/Chords100.jpg
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!

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).
alt text http://cs.smith.edu/%7Eorourke/MathOverflow/Chords100.jpg
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.