Have you ever wondered about the distinctive sweeping roof shape on certain buildings? These are flying eaves (飞檐 in Chinese; 추녀, chunyeo in Korean). They are not only supremely beautiful, they also serve a key functional purpose: when the eaves are upturned, they can welcome in more sunlight while still shielding from overhead rain. This additional sunlight helps dry out wooden homes after a rainstorm and hence prevent mold and rot.

I was interested in studying the shape of these eaves and modeling their rain-protecting and light-welcoming properties.  In this article, I present a simple mathematical model that shows how these properties change depending on roof shape.

The sun on the sloping roof

For simplicity, we will consider a two-dimensional rectangular house consisting of two walls, a floor, and a ceiling. The house is aligned with the sun, so that one wall lies to the east and the other lies to the west.

Let us also assume that the sun is infinitely far away. This allows us to model the sun's rays as perfectly parallel, and chart the sun's position throughout the day using a single angle measure \(\theta\). We can say that at 0° is daybreak, when the sun appears on the horizon; 90° is high noon, when it is directly overhead; and 180° is nightfall, when the it reaches the opposite horizon.

Note that in the figure, I have made the unusual choice to represent East as leftward. This unusual choice means that the sun will move from left to right throughout the course of the day, which I find convenient to visualize. The figure therefore depicts some time in the morning.

Next, let us add flying eaves to the roof.  We can model an eave as a curve in the plane, say a piecewise linear function like this one:

The rooftop contour can in general be any continuous curve, but to ensure that the eaves properly "fly" upward, we should require the contour to be a convex, increasing function. This prevents the roof from bending back onto itself, forming strange peaks, or sloping downward. The roof in the figure is a nice choice of convex, increasing function.

The umbrella equation

To calculate the effect of light and shadow on this roof, we can set up a 2D coordinate system where ground level is the line \(y=0\).  Supposing the roof is a piecewise linear function with endpoint coordinates \(\langle a_i, b_i\rangle\), how does the shadow vary with time of day \(\theta\)?

Note that each junction of the piecewise-linear roof casts its own shadow on the ground, forming a right triangle. The angle of the triangle is \(\theta\)—the angle of the sun—and the width of the triangle's base is \(b_i \cot(\theta)\) by basic trigonometry.

Putting together the shadows of all the junctions, we can see the whole shadow of the roof:

The figure above shows that the rightmost endpoint of the shadow is the projection of the rightmost edge of the house. This remains true throughout the morning, but in the afternoon—when shadows are cast toward the left—the rightmost end of the roof's shadow can be the projection of other endpoints instead:

Look at the figure above. You can visualize the qualitative behavior of the shadow as it changes throughout the course of the day:

• At daybreak, the shadow stretches westward into infinity.
• The shadow shortens until noon, when it lies directly under the roof.
• Starting in the afternoon, the light begins to reach the area beneath the eaves for the first time.
• As the sunlight reaches beneath the eaves, the boundary between light and shadow is a line segment. That line is parallel to the sun's rays and passes through one of the roof's endpoints.
• Because the curve is convex and increasing, this "terminator" line segment actually transits through each of the roof's endpoints in reverse order, from right to left.  It starts at the rightmost endpoint. It transitions between two consecutive endpoints just when the angle of the sun matches the slope of the roof segment between them.
• At some point in the evening, the sunlight finally reaches the western foundation of the house.  The light will begin to climb the walls of the house, until it illuminates the entire western wall and roof. They will remain entirely illuminated until sunset.

We know that whatever the piecewise-linear shape of the roof, the rightmost edge of the roof's shadow will be the rightmost projection of its individual segments. Using trigonometry, we can express this using the following formula, which I call the umbrella equation:

Umbrella equation (piecewise-linear). For a piecewise linear increasing roof with endpoint coordinates \(\langle a_i, b_i\rangle\), the shadow is a line segment on the ground with one moving endpoint \(\langle \alpha(\theta), 0\rangle\). That endpoint sweeps out a position given by: $$\alpha(\theta) = \max_i \left[a_i + b_i \cot(\theta)\right]$$

In fact, the same result holds if we generalize from piecewise-linear increasing functions to any convex increasing curve:

Umbrella equation (general form). For any convex increasing roof shape with coordinates \(\langle u, f(u)\rangle\), the shadow is a line segment whose moving endpoint sweeps out a curve \(\langle \alpha(\theta), 0\rangle\) given by: $$\alpha(\theta) = \sup_u \left[u + f(u) \cot(\theta)\right]$$

The interplay of light and rain

We now understand how a roof with a given shape lets in light throughout the day; it is governed by the umbrella equation. How about the rain?

If the day is not so windy, then rain falls vertically onto the roof (the same as the sun's rays at noontime.)  The shadow of the rain extends exactly as far as the rightmost part of the roof, regardless of time of day.

How the height of the roof matters. We can learn something by contrasting how the sun and the rain fall onto the roof.  For one thing, a higher roof allows more sunlight to come in, but does not affect the rain at all.  In an extreme case, a roof with extremely high eaves would shelter everything under it from the rain, while only minimally affecting the amount of sunlight in the afternoon. (Alas, in the morning, such a tall eave would leave the entire west side of the house in shadow.)

Have you ever noticed that mail trucks have their steering wheel on the curb side of the vehicle?  This puts mailboxes within arm's reach, so that postal workers don't have to get out of their vehicle when doing mail delivery rounds. As an added benefit, when they do need to get out of their vehicle, they can step directly onto the curb, instead of into traffic.

What a useful safety feature! Why shouldn't every car have curb-side driving, so that the driver can safely enter and exit from the curb side? For people driving alone, this seems like a total advantage. For people with passengers, it doesn't change how many people have to exit into traffic.

(And note that this isn't an issue of driving the car on the left or right side of the road; it's the entirely separate issue of which side to put the steering wheel on.)

I tried to think of justifications for putting the steering wheel on the center-line side.  Speculating wildly, I guessed it might be a hold over from horse-drawn carriages, where the passengers were in a higher hierarchical position,and so their comfort and convenience was prioritized.

After doing some digging, I discovered that the first cars did have curb-side driving—they were imitating the horse-drawn carriages, which also had curb-side driving. Ford changed to center-line side driving in 1908, citing that:

1. It's convenient for the front-seat passenger to exit onto the curb.
2. The center-line driver can better judge the distance to the center line and oncoming traffic.

But if the only real reason is to dodge oncoming traffic, perhaps we have all been disadvantaged by speed disease—the city-planning philosophy that gives fast-as-possible cars a monopoly over our road infrastructure, rather than enabling the broadest range of makeshift vehicles, bikes, animals, and pedestrians to be able to get where they need to go.  Avoiding oncoming traffic becomes a top-line priority only when everything is moving at such breakneck speed that conversation and negotiation with other drivers becomes impossible.

Cars are a complicated issue. It is useful to be able to move fast, particularly between cities, and cars provide both liberation and access to people who might not have other modes of transportation. But we should definitely ditch the speed disease, invest in better public transportation within our cities, and moreover design our cities so that lightning-fast vehicles are unnecessary within them. As long as we have cars, however, perhaps we should design them for our convenience. We should aspire to slow down so we can restore the steering wheel to its rightful place on the curb side of the car.

How do you cut a gemstone to make it shine brightest? Can you find an ideal shape using physical principles?

Gems are usually set into a ring or other piece of jewelry so that one main face (the "crown") is visible. Light enters the gem through the crown, where it bounces off of the interior facets and/or leaks through them. The brightness of a gem is determined by how much light is reflected back out through the crown instead of leaking out. Therefore, the simple rule for achieving shiny gems is:

Reflect as much light as possible back out of the crown.

This is basically a geometry problem: using mirrors and glass, you could design a triangular retroreflector that bounced light around in exactly this way. In 2D, you would make an isosceles triangle where the base side (the crown) is clear glass, and the other two sides are mirrored. By choosing good angles for the triangle, you could ensure that all light entering straight into the crown would bounce off the two mirrored sides and emerge back out. Problem solved.

For gemstones, however, there is also a materials problem: even polished gemstones are translucent, not mirrored. So, light entering the crown will tend to leak out of the bottom facets instead of bouncing---the surface behaves more like glass than a mirror. However, there is a solution: if light strikes the gemstone from an appropriately shallow angle, it will bounce perfectly instead of leaking through. This phenomenon is total internal reflection: when light that hits a surface at a shallow angle, the surface behaves like an essentially perfect mirror. (When you dive into a swimming pool and look up at the surface of the water, total internal reflection explains why the surface forms a perfect silvery mirror except for a small circular window.)

Every material has its own critical angle, which is determined by the material's refractive index.

Returning to our triangular model, the material's critical angle will determine how steep we should make the sides of the gemstone. We want to make it steep enough so that the walls of the gem become mirrored and all the light entering straight into the crown will be reflected out. We are looking for a design parameter: what angle to make our triangle. Gemologists refer to this design parameter as the pavillion angle, labeled as \alpha in the figure below. We have four constraints on \alpha altogether: two geometric constraints and two material constraints.

1. The angles \(\theta_1\) and \(\theta_2\) represent reflections, so they must lie between 0 and 90 degrees.
2. By triangle geometry, \(\theta_1=\alpha\), and \(\theta_2 = 180^\circ -3\alpha\).
3. In order for the first bounce to behave like a mirror, \(\theta_1\) must exceed the material's critical angle.
4. In order for the second bounce to behave like a mirror, \(\theta_2\) must exceed the material's critical angle.

These four constraints, along with the definition of critical angle \(\theta_c = \arcsin(1/n)\) in terms of refractive index n, enable us to find the acceptable range of angles for making our shiny gemstone.

In the following graph, I have depicted the four constraints and their range of solutions:

Fun Applications

In short, we have learned—to first approximation—that you make a gemstone shine brightest by making it into a retroreflector with two internal rotations. You can dream up some interesting consequences of this fact, a few of which I enumerate below:

• Gems are like other retroreflectors. Gems work by using mirrored surfaces to send incoming light right back out, the same principle as eyeshine in cats and other animals, and those bright retroreflectors on highways.
• Miscut gems become windows. If you cut the gem at the wrong angle, the bottom facets will leak light instead of reflecting the light back up. Gemologists refer to this unfortunate event as windowing the gem. We now understand the physics behind it: instead of becoming total internal reflectors, the facets of a miscut gem remain translucent like windows.
• You can't make gems out of certain materials. Our recipe is for making a gemstone using two total internal reflections. If a material's refractive index is below \(\sqrt{2}\approx 1.41\), you can't achieve those two internal reflections.
• A bigger index means a wider range. Materials with greater refractive indices have more flexible ranges of pavillion angle.
• You can quench fire with water. The shape of a gem is tailored to the refractive index of the material and also, implicitly, the refractive index of air. If you put a loose gem into water, its facets stop behaving like perfect mirrors and it loses all of its sparkle.
• Sunlight is best. In our approximation, we only imagined parallel light rays coming straight into the sun. Of course, most lighting environments have diffuse light coming in from all directions. A superb example of parallel light is sunlight; hence gems will look their best when you're looking straight into the crown, and the sun's rays shine directly into the crown as well.
• You can make cones, too. In 3D, instead of making the pavillion out of triangular facets, you could simply lathe the gem into a cone of the appropriate angle. This would achieve the total internal reflection just as well as discrete facets. It wouldn't have sparkling facets, but I expect it would have its own smoothly luminous beauty.
• You can't see through a gem. Here's one way to confirm that gems use total internal reflection: you can't see through it when you're looking through the crown! This is most obvious on a large, loose, translucent gem: hold the gem up to a colorful surface and look through the crown. You won't be able to see the colorful surface through the gem.

Celtic knots, or interlace, are a beautiful, ancient art form with interesting symmetries and topological properties:

It turns out that you can follow a recipe to turn any planar graph into its corresponding knotwork, or vice-versa. (You can follow this recipe, the Mercat procedure, by hand; alternatively, it's precise enough that you can implement it as a computer program.)

With this recipe in hand, I began seriously wondering what some of my favorite and familiar graphs would look like as knotwork. What about the triforce symbol? Or a square? What about a cube? Oh! And what about the rest of the platonic solids as well?

Yes, that was a good challenge. The platonic solids are fun to try to visualize (I hadn't learned how to effectively visualize yarn wrapping around 3D shapes, so I had to try several ways of drawing them in two-dimensional flatland; see below.). After much trial and error, I got the following glorious series of pictures:

As you can see here,

1. Each knotwork consists of interlocked circles (3 for the tetrahedron; 4 for the cube and octahedron; 6 for the dodecahedron and icosahedron).
2. Corresponding pairs of dual shapes have the same number of circles (cube-octahedron, dodecahedron-icosahedron). They vary based on how the circles are arranged; e.g. whether there's a central circle.
3. Each knotwork has various symmetries including rotational and reflective, as well as the over-under pattern of string crossings.
4. The overlapping circles create regions with recognizable shapes. For example, the icosahedron's knotwork is made up of five-sided and three-sided regions (with a pentagon in the middle). Its dual, the dodecahedron, is made of the same shapes, but with a triangle in the middle. You can see these shapes more clearly when the regions are colored in a checkerboard pattern (see below). The cube and octahedron include four-sided regions.
5. There are other patterns if you look—for example, how many stars can you spot in the icosahedron and dodecahedron knotwork below?

Mathematical remark: To count the number of threads, you can use the formula: \(|T(−1,−1)|=2^c−1\) where T is the Tutte polynomial of the planar graph, and c is the number of threads. Incidentally, because the dual of a graph has the same Tutte polynomial with x and y exchanged, this implies a full generalization of the result we discovered here: every graph has the same number of knotwork strands as its dual.

Mathematical remark: As shown in the checkerboard-shaded pictures, the knotwork for each polyhedron divides space into two kinds of shape, e.g. triangles and pentagons. The two shapes are apparently directly related to the Schlaffi symbol for the polyhedron—that is, the shape of each face, and the number of faces meeting at each vertex.

1 How I generated these

To generate this knotwork, you start with one of the figures such as the icosahedron:

You want to stretch it so that you can draw it on a flat piece of paper without any of the lines crossing. In this particular case, you can take the back-face triangle and pull all of its vertices out from behind the icosahedron. The result is a planar graph:

Now we can apply the Mercat procedure to draw threads that cross in pairs at the midpoint of every edge in the graph. The result is a bit messy, but if you color in each of the threads in a different color, you see that the knotwork is made up of simple (non-self-intersecting) closed loops.

To straighten out the wobby loops into perfect circles, all I did was arrange some colored circles by trial and error into positions that had the same symmetry as the knotwork. I then checked whether my circles had the same crossings as the knotwork, and made the same shaped regions (triangles, pentagons). The result is as you've seen, and you can repeat this process for any of the other polyhedra:

The Magic: The Gathering card game has evolved its own strange and wonderful dialect. Although the rules on each card were originally written in standard informal English, the language has been shored up over time so that it is more technically precise and unambiguous—a kind of specialist, almost legalese, offshoot of English. The break with standard English grammar is striking and profound.

For example, Magic has a new determiner, "target", that standard English lacks (ex: Destroy target land) and the word permanent can be used as a noun but never as an adjective (ex: Permanents you control can't block).

And the differences go beyond mere tweaks to the lexicon, i.e. just adding new words or new ways of using words. These differences pervade the grammar at a deep level: Certain phrasings, while innocuous in English, sound wrong to anyone who has played Magic long enough to get the knack of it. Compare¹:

• All creatures have haste.
• * Creatures have haste.
• Red creatures have haste.
• * All red creatures have haste.

These phrasing rules are—to my knowledge—not stated explicitly anywhere. They are learned apparently without direct instruction and without most players even noticing it. And while the lexicon was carefully put together by hand, the grammar appears to have emerged organically. Nonetheless, I claim that Magic players generally all acquire an ear for these rules, and generally have consistent judgments about what sounds strange.

I'm curious about what these rules are. This article is an attempt to do some linguistic investigative work to characterize the strange and wonderful dialect of Magic. I think it would be interesting to do a proper linguistics study; in lieu of this, I have surveyed my Magic-playing friends to corroborate my guesses. I have also made use of the fact that Magic has a de facto exhaustive corpus—namely, the text of all cards that have ever been printed. I use this corpus testimony to confirm that certain phrasings are allowable, and (although a productive grammatical system can produce an infinite variety of things to say) that when I label a phrasing as unallowable, it genuinely doesn't occur anywhere.

I start the linguistic investigation here in this article, but Magic's grammar is so complex, I can hardly cover everything. I hope that others might be inspired to take on some aspect of this work. There is much work to be done.

Static abilities

Scoping quantifiers: All creatures have haste.

Let's start with a simple static ability "All creatures have haste". Consider these variations:

1. [?] All creatures have haste
2. [?] Creatures have haste
3. [?] Red creatures have haste
4. [?] Creatures you control have haste
5. [?] Red creatures you control have haste
6. [?] All red creatures have haste
7. [?] All creatures you control have haste.

If you're a fluent speaker of Magic, I suspect some of these sentences sound better—more correct—than others. Before reading further, feel free to take a moment to consider which of these sentences sounds a little off; we can see if our judgments agree.

Here are my judgments; in the case of positive judgments, I've attempted to find a card as supporting evidence. Although it was not always possible to find an exact match, the card is always a clear and compelling relative—one that merely uses White instead of Red, or flying instead of haste, for example.

1. All creatures have haste (Concordant crossroads)
2. * Creatures have haste
3. Red creatures have haste (Aysen Highway)
4. Creatures you control have haste. (Archetype of Imagination)
5. Red creatures you control have haste. (Bloodmark Mentor)
6. * All red creatures have haste.
7. * All creatures you control have haste.

and the same variations with the subtype Sliver added:

1. All Sliver creatures have haste. (Battering Sliver)
2. * Sliver creatures have haste.
3. Red Sliver creatures have haste.
4. Sliver creatures you control have haste. (Belligerent Sliver)
5. Red Sliver creatures you control have haste.
6. * All red Sliver creatures you control have haste.
7. * All Sliver creatures you control have haste.

What distinguishes the good-sounding cases from the bad-sounding ones? I suggest the following theory:

• The main noun (creatures) must have some scoping quantifier attached to it. Intuitively, Creatures have haste doesn't sound specific enough---which creatures have haste?
• The scoping quantifier can be any of these: The universal quantifier ("All"), a color ("Red"), a control status ("__ you control") or an ability clause ("__ with flying").
• The quantifier "All" can't co-occur with any of the other qualifiers. Everything else can happily co-occur.
• Type descriptors, such as "Sliver", are totally optional—they aren't a kind of scoping quantifier like "all" "red" or "you control". You can always include them and always leave them out.

Using the Python Natural Language Toolkit, you can define a feature-based grammar to account for these observations. (See the Appendix at the end of this section for file details.)

To codify the static-ability theory here, I introduce a binary feature +definite which is conferred by each of the scoping quantifiers and inherited upwards (so any phrase containing a +definite constituent is itself definite). The grammar thereby imposes the "scoping quantifier" requirement by requiring the overall sentence to be +definite. Finally, the word "All" confers definiteness, but can only be paired with a -definite (definite-lacking) phrase.

(I use an irritating contrivance to ensure that each of the quantifiers occurs at most once: the quantifiers are considered in the order "_ with/out [ability]", "_ [player] controls", "[color] __", "[type descriptor] __." As an unfortunate side effect, this makes the rules-list longer and more cumbersome than it needs to be. Perhaps I will rewrite it with a more elegant approach later.)

% start S
S -> StaticAbility

StaticAbility -> DefinedClause[num=?n, +definite] HasAbility[num=?n] Ability

DefinedClause[num=?n, +definite] -> 'all' WithAbilityClause[num=pl, -definite]
DefinedClause[num=?n, +definite] -> 'other' WithAbilityClause[num=pl]
DefinedClause[num=?n, definite=?d] -> WithAbilityClause[num=pl, definite=?d]

WithAbilityClause[num=?n, +definite] -> ControlledClause[num=?n] 'with' Ability | ControlledClause[num=?n] 'without' Ability 
WithAbilityClause[num=?n, definite=?d] -> ControlledClause[num=?n, definite=?d] 

ControlledClause[+definite, num=?n] -> ColorClause[num=?n] 'you' 'control'
ControlledClause[definite=?d, num=?n] -> ColorClause[definite=?d, num=?n]

ColorClause[+definite, num=?n] -> Color SubtypeClause[num=?n]
ColorClause[definite=?d, num=?n] -> SubtypeClause[num=?n, definite=?d]

# Subtypes don't confer definiteness 
SubtypeClause[definite=?d, num=?n] -> 'sliver' FinalClause[definite=?d, num=?n] | FinalClause[definite=?d, num=?n]

FinalClause[definite=?d, num=?n] -> Permanent[num=?n,definite=?d]

Permanent[num=sg] -> 'permanent'| 'land'| 'creature'| 'artifact'
Permanent[num=pl,-definite] -> 'permanents'| 'lands'| 'creatures'| 'artifacts'
Permanent[num=pl,-definite] -> 'slivers'

Ability -> 'haste' | 'flying' | 'vigilance' | 'reach' | 'defender' | 'lifelink' | 'deathtouch' | 'menace'

1.2 Negative polarity: Creatures can't block.

In the previous section, we showed how the "…have haste" static ability requires some sort of scoping quantifier such as "All" or "Red" or "_ you control". As we will see, the "…can't block" predicate has a different set of requirements:

1. * All creatures can't block.
2. Creatures can't block. (Bedlam)
3. Red creatures can't block. (Awe for the Guilds, Flooded woodlands)
4. Creatures you control can't block. (Blightbeetle, Cosmotronic wave)
5. Red creatures you control can't block. (Deepchannel Mentor)
6. * All red creatures can't block.
7. * All creatures you control can't block.
8. Slivers you control can't block (Doomed Artisan)
9. Sliver creatures can't block (Ruthless invasion) (?)

In this context, apparently all scoping quantifiers are now optional—they can always be included or left out. The one exception is "All", which is completely forbidden.

Why should "All" be completely forbidden in this context? To my ear, "All" sounds wrong in the negative context created by "can't". In standard English, this happens with words like "somewhat" that are ungrammatical in a negative environment:

• I liked the movie somewhat. (Standard English)
• * I didn't like the movie somewhat. (Standard English)

In fact, we've got some evidence that Magic's "All" is a positive-polarity item. Contrast these two abilities:

• All red creatures can block […] (Frenzied Saddlebrute)
• * All red creatures can't block.

To accomodate this theory, we can introduce a new lexical feature +polarity. The "can't" phrase introduces negative polarity -polarity, while "All" is a word that must bind to a phrase with positive +polarity and (as already established) negative -definite-ness.

Here's the new rule for static abilities, updated accordingly:

StaticAbility -> DefinedClause[-polarity] "can't" "block"
StaticAbility -> DefinedClause[num=?n, +definite] HasAbility[num=?n] Ability

DefinedClause[num=?n,+definite, +polarity] -> 'all' WithAbilityClause[num=pl, -definite]

2 Appendix: Python nltk

The grammars in this article are written using the Python Natural Language Toolkit (nltk). In the general setup, I have a file containing the grammar mtg.fcfg which is written in a kind of context-free grammar syntax. I also have a python script that loads the grammar and uses it to test various sentences. For example:

import nltk

from nltk import grammar, parse
cp = parse.load_parser('mtg.fcfg')

sentences = [
    ("creatures have haste", False),
    ("all creatures have haste", True), # Concordant crossroads
    ("creatures you control have haste", True),
    ("red creatures have haste", True), # Aysen Highway
    ("all red creatures have haste", False), 
    ("all creatures you control have haste", False),
    ("red creatures you control have haste", True ), 
    ("sliver creatures have haste", False),
    ("all sliver creatures have haste", True),
    ("all red sliver creatures you control have haste", False),
    ("red sliver creatures you control have haste", True),
    ("other creatures have haste", True),
    ("slivers you control have haste", True),
    ("all slivers have haste", True),
    ("creatures with flying have haste", True), #Empyrean Eagle #Smog Elemental

    ("creatures can't block", True), # Bedlam
    ("all creatures can't block", False),
    ("other creatures can't block", True),
    ("red creatures can't block", True),
    ("slivers can't block", True)
]

for s,judgment in sentences:
    tokens = s.split()
    trees = cp.parse(tokens)

    has_parse = None
    for t in trees :
        has_parse = t
        break
    if has_parse :
        print(s)
        # print(t)
    else :
        print("*", s)

    if bool(has_parse) != bool(judgment) :
        print("\t\t<<<Unit test failed")
        ```

Footnotes:

¹ In this article, following standard linguistic conventions, I mark sentences with an asterisk (*) when I think they sound strange (ungrammatical); unmarked sentences sound right.

The conic sections are a family of shapes consisting of parabolas, hyperbolas, and ellipses. Conic sections show up in many scientific applications; for example, celestial orbits trace out different conic sections depending on their energy^[1]. The shadow cast by a sundial's "spike" (gnomon) traces out a different conic section depending on latitude and time of year^[2]. And mirrors shaped like conic sections have important optical properties for focusing light^[3].

It's therefore useful to be able to take some imprecise physical measurements and fit a conic-shaped curve to them. In this article, I provide some code for doing this. The figure above illustrates fitting some real data points for a sundial; the algorithm finds the hyperbolic shape shown.

Algebraically, conic sections are the graphs of the equation: $$Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0$$

(It's just any general polynomial you can make involving x and y where no term has a combined exponent bigger than two.) There is some beautiful linear algebra under the hood; one useful fact is that the discriminant \(B^2-4AC\) is either positive, negative, or zero, which tells you whether the shape is an ellipse, hyperbola, or parabola.

To measure how well a particular conic section fits your data \(\langle
x_i, y_i\rangle\), you might imagine a straightforward algorithm: compute \(A x_i^2 + Bx_iy_i + C y_i^2 + D x_i + E y_i + F\) for each data point, square those values and add them up, then see how far away the sum is from zero. To find the optimal fit, vary the coefficients to make this sum as close to zero as possible.

This basic approach almost works, despite the search space being unstable^[4]. You can modify it to make it more stable and to allow the user to specify a target conic type (hyperbola, parabola, or ellipse) in advance. In a paper by Nievergelt, the author describes how to do this. I implemented the suggested algorithm in Python, as shown below.

Interestingly, the algorithm gets less stable the better the data fit a particular conic; a little empirical noise is useful. Because my target application (determining whether a blackbox function represents a conic) involved extremely accurate conic sections, this threw off my results. So I modified the algorithm slightly. Where the algorithm uses an SVD decomposition to decide whether the points all lie on a line, I use the Theil-Sen estimator^[5].

I also found a few typos in the manuscript, which when fixed allowed me to exactly reproduce the curves in the paper.

Source code

from numpy.linalg import svd, qr, solve, det
from numpy import array, matmul, float64, transpose # , allclose, matmul, float64
from math import sqrt

#### Given a list of 2D points, return an array
#### describing the best-fit conic. Returns something special in the
#### case of degenerate conics (e.g. straight lines)

# See paper: Yves Nievergelt, "Fitting conics of specific types to
# data"


SMALL = 10**-12
sqrt2 = 2**0.5

TYPE_HYPERBOLA = "hyperbola"
TYPE_PARABOLA = "parabola"
TYPE_ELLIPSE = "ellipse"


def centered(points) :
    """Subtract the average from the (x,y) pairs."""
    xs_uncentered = [x for (x,y) in points]
    ys_uncentered = [y for (x,y) in points]

    x_center = sum([x for x in xs_uncentered])/len(points)
    y_center = sum([y for y in ys_uncentered])/len(points)

    xs = [x-x_center for x in xs_uncentered]
    ys = [y-y_center for y in ys_uncentered]

    return list(zip(xs,ys)), (x_center, y_center)


def collinearity(points) :
"""Return a number indicating how very nearly the points follow a line. Zero indicates perfect fit."""
    # This is a very hackish parody of Theil-Sen estimator. I'm using
    # it because SVD sometimes fails to converge, and besides for this
    # application I care only about detecting near-perfect
    # fits. Returns the mean square error of the estimator, as a
    # number.

    (x0, y0) = points[0]

    average_x_deviation = sum(abs(x-x0) for (x,y) in points[1:])/len(points)
    if (average_x_deviation < SMALL) :
        # VERTICAL LINE
        return 0

    slopes = sorted([(y-y0)/float(x-x0) for (x,y) in points[1:]])
    median_slope = slopes[int(len(slopes)/2)]
    
    intercepts = sorted([y - median_slope*x for (x,y) in points[1:]])
    median_intercept = intercepts[int(len(intercepts)/2)]
    
    average_deviation = sum((y-median_slope*x-median_intercept)**2/len(points)
                            for (x,y) in points)
    return average_deviation


def smallest_singular(M, compute_singular_vector=True) :
    """Return a pair containing the smallest singular value of M and a
corresponding singular vector.
    """

    if compute_singular_vector: 
        _, s, Vh = svd(M, full_matrices=True)
        return s[-1], Vh[-1]
    

def fit_conic(points, desired_type=None) :
    points, center = centered(points)

    matrix_monomials = array([
        [1, x, y,    y*y-x*x, 2*x*y, y*y+x*x]
        for (x,y) in points])

    # ---- Check for degenerate conic lying on a single line
    if (collinearity(points) < SMALL) :
        return None


    # ---- Perform decomposition
    submatrix = matrix_monomials[:,:3] # (1,x,y)
    q,r = qr(submatrix, "complete")

    
    R_full = matmul(transpose(q), matrix_monomials)
    RA = R_full[:3, 0:3]
    RB = R_full[:3, 3:6]
    RC = R_full[3:, 3:6]
    _, vec_smallest = smallest_singular(RC)

    # ----- Determine type of conic
    Z = array([[-1,0,1],
               [0,sqrt2,0],
               [1,0,1]]) / sqrt2
    D = array([[-1,0,0],
               [0,-1,0],
               [0,0,1]])/4

    A_det = transpose(vec_smallest) @ D @ vec_smallest
    A_trace = vec_smallest[2]

    conic_type = TYPE_PARABOLA if (abs(A_det) < SMALL) else TYPE_ELLIPSE if A_det > 0 else TYPE_HYPERBOLA


    # ---- Adjust answer if it doesn't match desired conic type (not
    # ---- implemented yet)
    
    if(False and desired_type == TYPE_PARABOLA) :
        # "desired type" not implemented yet.  also not necessary for
        # this application b/c empirical points are expected to be
        # extremely unambiguously close to particular conics.
        
        pass
    else :
        q = vec_smallest


    # ------ Solve for conic coefficients
    ret = solve(RA, -1 * (RB @ q)) # c, *two_b

    params = [*ret, *q]

    conic_coeffs = [ params[5]-params[3],
                         2*params[4],
                         params[5]+params[3],
                         params[1],
                         params[2],
                         params[0]]

    
    fit  = sum([x**2 for x in matmul(matrix_monomials, array(params))])/len(points)


    A,B,C,D,E,F = conic_coeffs

    
    quadratic_form = array([[A, B/2],[B/2,C]])

    full_form = array([[  A, B/2, D/2],
                       [B/2,   C, E/2],
                       [D/2, E/2,   F]])

    if(abs(det(full_form)) < 1e-8) :
            # degenerate conic
            return None
    
    
    u,s,vh = svd(quadratic_form)

    K =  -det(full_form)/det(quadratic_form) if det(quadratic_form) != 0 else None

    axes = None
    try :
        axes = [(K/x)**0.5 for x in s.tolist()]
    except Exception :
        pass
        
    return {"type" : conic_type,
            "coeffs" : conic_coeffs,
            "fit" : fit,
            "axes" : axes,
            "diagonalizer" : vh.tolist(),        
    }, center

The card game Push is played between two people. A deck is shuffled then divided in half, with each player receiving a half (face down). During a round, both players reveal the top card of their deck; the high card scores a point. (Ties are handled in a special way.) The winning player is whoever has the most points after all of the cards have been revealed. Obviously players can control the outcome of the game by magically manipulating probabilities.  In this brief note, I discuss optimal strategies for increasingly complex variations of the game. I describe the variant in one paragraph, followed by the solution. You should feel free to read the variant and discover the solution on your own.

1 Two full decks

Problem: Suppose you are playing a simpler version of this game where you and your opponent each get a full deck of cards. Suppose the cards are numbered, say 1 through 52. Finally, suppose you know the exact order of your opponent's cards, which will not change. How should you, through tychokinesis, order your cards so as to achieve the highest possible score?

Solution: The [only?] optimal solution is whenever your opponent plays a card, you play the card ranked one above it. The only card for which this strategy is impossible is when your opponent plays the highest-ranked card in the deck (which is unbeatable) in which case you play the lowest-ranked card in the deck. This "rotate by one" strategy is optimal because you win every round except the one in which your opponent plays a card that can never lose and you match it with a card that can never win.

2 Splitting one deck

Problem: Now suppose we split a single shuffled deck in half, giving one half to you and one half to your opponent. Suppose you still have perfect knowledge in this variant: you know exactly the shuffled order of your opponent's cards, which will not change. Consequently, you can determine which cards you've been dealt. How should you, through tychokinesis, order your cards so as to achieve the highest possible score?

Solution: Note that we are trying to decide which cards in your deck to match against which cards in your opponent's deck. Once we've decided on that matchup policy, it doesn't matter how the opponent's deck is shuffled; just play the corresponding matched card. Here's an optimal strategy: You know which cards you have and which cards your opponent has. Mentally arrange your deck in ascending order of rank, and arrange your opponents cards the same way. Look at your opponent's highest-ranked card, and pair it with the lowest-ranked card you have that can beat it. (If none of your cards can beat it, pair it with your lowest-ranked card overall.)  Eliminate those two cards from consideration and repeat the matching process. This strategy is at least locally optimal because whenever you play a high card, you win, and whenever you don't, it's impossible to win. I suspect it is globally optimal as well. This strategy is also very general: it subsumes the strategy from the previous section, and actually applies to any two decks of the same size (not just decks created by splitting a single deck in half).

3 Opponent plays at random

Problem: Now suppose you only know the contents, but not the order, of both decks: we split a single shuffled deck in half, giving one half to you and one half to your opponent. You know which cards each person has, and your opponent's cards are in a fixed but unknown order. How should you, through tychokinesis, order your cards so as to achieve the highest possible score?

Solution: Perhaps surprisingly, you can't do anything strategic against a random opponent. Regardless of your chosen strategy, your expected score is equal to the probability that you win a random matchup between one of your cards and one of theirs, times the number of cards you have. You can prove this by induction, using an n-by-n matrix which has a 1 in entry (i,j) if your ith card beats their jth card and a 0 otherwise. Regardless of strategy, your expected score is equal to the sum of the entries in this matrix, divided by n.

4 Paying for entropy

Problem: Next, we introduce tychokinetic costs. Again, a shuffled deck is split in two, with both players receiving a half. You know the contents of both decks, and as with the deterministic variant, suppose you know the fixed order of your opponent's deck. Normally, when you play a card, you are drawing uniformly from the set of all cards you haven't played yet. Using tychokinesis, you may instead choose to draw uniformly from a smaller subset. The smaller subset consists of your choice of one or more cards that you haven't played yet. When drawing from a smaller subset, you must pay an entropy cost of (n/k) log(n/k), where k>0 is the size of the subset and n is the total number of unplayed cards in your deck. Suppose you just want to win, not necessarily by the largest possible margin. Find the strategy that minimizes the amount of entropy you pay for, subject to the condition that you still win the game if possible.

Solution: ???

5 Adversarial zero-cost

Problem: In the ordinary game, you and an opponent have a face-down shuffled deck split between you. You draw the top card of your deck and your opponent does the same; then you reveal both cards and whoever's card has higher rank wins a point. The two cards are discarded and the process is repeated. The winner of the game is whoever has the most points when the decks are depleted. (If we suppose players do not know the contents of either deck, it is equivalent and conceptually simpler to model the game with both players drawing cards from a single face-down deck instead.) Now for tychokinesis. Before revealing a card, you may secretly, and at no cost, choose any subset of two or more specific cards that haven't been played yet. Your card will be drawn uniformly at random from this subset. Your opponent may do the same. (Neither of you has any information about whether the other person has used tychokinesis or which subset they've chosen, and the choice of subset is made before any cards are drawn that round.)  Cards are guaranteed by the laws of physics to be distinct. Is there an effective strategy for cheating that improves your chances of winning over playing fairly, or is the best strategy to play fairly?

Solution: If you draw the card of highest rank, you win with certainty. If you draw the card of next-highest rank, you win unless your opponent draws the card of highest rank. If you draw any card of lower rank, you are less likely to win against any particular subset of cards; therefore, to maximize your expected winnings, you should choose the subset consisting of the two highest-ranked cards. By symmetry, so should your opponent. Also by symmetry, your probability of winning when both players use this strategy each round is 50%. Finally, each round, there are always at least two cards remaining in the shared deck. Because this strategy does not otherwise depend on which cards are in the deck, this strategy is optimal each round and your probability of winning the game overall is 50%.

Other variants

1. Minimax: You and an opponent play the game adversarially. Contents of both decks are unknown. You and the opponent may each pay entropy to draw from a smaller subset of /two/ or more cards that haven't been played yet. (You and your opponent are guaranteed by the laws of physics to draw distinct cards.)  Win, according to some metric of energy and points.
2. Energy profiles: If you and your opponent have available entropy budgets of H_1 and H_2, respectively, does this uniquely determine your expected probability of victory? (Or is uniform play still optimal so that the budget is never used?)

As you may know, the Pokémon type system consists of (approximately) seventeen different types, each with different comparative advantages over the others like a more elaborate version of rock-paper-scissors. In the Pokémon video games, the types and their advantages are hardcoded as laws. But if you adopt the view of someone who actually lives in the Pokémon universe, those advantages would have to be scientifically measured and discovered.

How would you empirically determine the types and their advantages? What information would you need to be able to measure, and how many measurements would you need to get a reasonably accurate picture? What would it take to be reasonably sure you had discovered all existing types and interactions? Questions like these comprise a field of study I call empirical Pokémon typing, and this article contains a few preliminary results.

Problem #1: Relating attacking and defending types

In our first result, I'll point out a feature of the type-effectiveness system that is surprisingly hard to discover empirically. We are told in the game that attacks have types, and Pokémon species have types, and that these types come from the same list: there are Fire-type attacks and Fire-type Pokémon. If you weren't told this relationship in advance, how could you discover it empirically?

There's one particularly good way to do it: same-type attack bonus (STAB) directly shows the link between an attack type and a Pokémon type, because the Pokémon using that attack gets an additional bonus. You could set up an experiment to identify STAB and therefore associate attack types with Pokémon types. I discuss this method in the next section.

You could also use an indirect method, such as assuming that a Pokémon shares a type with most of the attacks it learns. Then you could compute the appropriate learnset statistics to guess which attack types are associated with which Pokémon. This, however, is less decisive than STAB.

It turns out, actually, that STAB is the only direct method: without STAB, there is no way to empirically associate Pokémon types with attack types. Details follow.

Here's the basic structure of an empirical Pokémon typing experiment: You start with a group of Pokémon subjects, each of which knows some attacks. You have each Pokémon use each attack against each other Pokémon, and somehow measure the resulting susceptibility (type effectiveness).

Tabulating the results, you could fill out a table of empirically-determined type effectiveness values. The rows of the table will be attacks, and the columns of the table will be Pokémon species. Duplicate rows or duplicate columns suggest that two attacks / species are of the same type.

This effectiveness table is the source of our data. Now we must make a theory of how many types exist and what their effectivenesses are. To start, let's first approach the problem in a setting with the following simplifying assumptions:

1. No dual types. Each Pokémon has exactly one type. This way, we don't need to disentangle whether we are dealing with a dual type or not.
2. Our measurements are perfect. Our data has no errors because we can perfectly measure the susceptibility of each Pokémon to each attack.
3. We can perfectly distinguish different species and types. Assume we are never confused about whether two species of Pokémon are the same, or whether two attacks are the same. (No crocodile vs alligator ambiguity)
4. No STAB. Type effectiveness is completely determined by the attack type and defending Pokémon type. In particular, there are no other factors like same-type attack bonus ("STAB"). (Same-type attack bonus amplifies the type effectiveness of an attack based on the type of attacking Pokémon.)

Under even these simplifying conditions, we have a surprising negative result:

Without same-type attack bonus (STAB), there is no principled way to identify types of attack with types of Pokémon based on susceptibility measurements alone.

In other words, using the effectiveness table, you could divide the Pokémon species into groups that seem to share the same type. And you could divide the attacks into groups that seem to share the same type. But there would be no principled way to match up the Pokémon species types with the corresponding attack types.

This means that if you weren't told that the attacks we call Fire-type (attacks that are super-effective against Grass defenders and ineffective against Water defenders) should be identified with the type of Pokémon we call Fire-type (that are vulnerable to Ground-type attacks and resistant to Ice-type attacks.), you would have no way to infer that information from the susceptibility type chart alone.

Or put another way: if I reorder the rows and columns of the ground-truth type susceptibility table, then erase the type labels, there is no principled way for you to figure out which attacking types match which defending types just by looking at the chart.

Proof: Attack types and species types are unrelated.

This negative result can actually be viewed as a consequence of a theorem from linear algebra, which states that there is no canonical basis for the dual of a vector space. Put more colloqually, if you cannot measure the similarity of one type to another, then there's no relationship between attacking and defending types.

You can show that this result applies by showing that Pokémon type effectiveness has the structure of a linear (vector) space, as follows.

Attack effectiveness in practice is a multiplicative factor. Possible effectiveness values consist of 2x, 1x, 0.5x, and 0x. In order to apply linear algebra, which is additive instead of multiplicative, we will not deal with effectiveness values directly, but instead with (base 2) logarithms of effectiveness values; I call these susceptability values.

If there are n Pokémon types, then we can form an \(n \times n\) effectiveness matrix \(\mathbf{S}\) of susceptibility values. Using \(\mathbf{S}\), you can compute how effective an attack will be against a particular Pokémon through straightforward matrix multiplication: The defending Pokémon's type(s) are encoded in a length-n column vector \(\vec{d}\). Each entry is 1 if the Pokémon has that type, or 0 if the Pokémon does not^[1]. The product \(\mathbf{S}\cdot\vec{d}\) is then a column vector neatly listing the Pokémon's susceptibility to each type.

If \(\vec{a}\) is a length-n row vector describing the type of the attack, then \(\vec{a}\cdot \mathbf{S}\cdot \vec{d}\) is a single number indicating the susceptibility of the specific Pokémon with type \(\vec{d}\) to the attack of type \(\vec{a}\). Next, the collection of all theoretically possible Pokémon type combinations forms an n-dimensional vector space. It's the collection of all possible \(\vec{d}\) vectors. There's one dimension for each type, and the value of each component tells you how many copies of that type a Pokémon has. Because we'll need to distinguish attacking and defending types, we might call this the defending type space. An attacking type is a map assigning a susceptibility value to each of the n defending types. Susceptibility values add, so that a Pokémon with multiple types has the sum of the susceptibility values of the individual types---this means that an attacking type is a linear map assigning a susceptibility value to each of the n defending types. Hence the space of all theoretically possible attacking types is a space of linear functionals on defending types; it's the dual of the space of defending types.

But there is no canonical way to associate the basis of a mere vector space (such as the single types in defending type space) with a basis in the dual space (such as the n different attacking types.) It follows that, without additional structure, we have no principled way to identify defending types (a vector space) with attacking types (functionals on that space).

Irrational factors and same-type attack bonus

As I've pointed out, same-type attack bonus (STAB) is the only direct way to identify which attacking and defending types should be identified with each other.

You can empirically determine STAB using a straightforward experimental setup like this: make an empirical susceptibility table with attacking species+move along one dimension and defending species on the other, then finding two rows that are identical except that when Pokémon A performs attack B against Pokémon C, there is a boost to susceptibility that does not occur when Pokémon A' performs that same attack against Pokémon C. This is conclusive evidence of STAB, because the difference is not in the type of attack or the type of defending Pokémon, but the type of attacking Pokémon.

But in fact, there's an even easier analytic route to identifying STAB: if we assume that STAB confers a multiplicative factor of 1.5 as it does in game, then its logarithmic susceptibility value is \(\gamma \equiv \log_2(1.5)\approx 0.5849\). This is an irrational number, and it means that we'll get a row of irrational susceptibility values in our susceptibility table when, and only when, STAB occurs. Details follow.

In practice, if we can make some assumptions about allowed susceptibility values, there is an even easier analytic route to determining STAB which does not require more than one attacking Pokémon. The idea is that STAB yields irrational susceptibility values instead of rational ones, and so is immediately identifiable.

The possible monotype effectiveness values are [2x 1x 0.5x 0x] which correspond to susceptibility values of [1 0 -1 -∞]. We could consider alternative possible values for STAB, but in the games it confers 1.5x effectiveness, or a susceptibility of \(\gamma \equiv \log_2(1.5)\approx 0.5849\). This susceptibility value is irrational (because if \(\gamma = p/q\) is rational then \(2^{p/q} = 1.5\) so \(2^{(p/q)+1} = 3\) so \(2^{p+q} = 3^{q}\), contradicting the unique factorization of integers.) But natural susceptibility values (those unaffected by STAB) are all integers (or infinite). Therefore, if we are told that natural susceptibility values are all integers (or infinite) and are given precise empirical susceptibility measurements, we can always identify STAB because it will produce irrational susceptibility values wherever it occurs.

In fact, if we know that the STAB component is irrational---even if we don't know its exact value---we can compute its value uniquely from the table: if the susceptiblity is an integer combination of STAB and non-STAB susceptibilities (\(m + n\gamma\)), note that these coefficients are unique; if \(m + n\gamma = m^\prime + n^\prime\gamma\) then \((m-m^\prime) = (n^\prime-n)\gamma\). If \(n\neq n^\prime\), then \((m-m^\prime)/(n-n^\prime) = \gamma\)---but the left side is a rational number and the right side is irrational, a contradiction. Therefore \(n=n^\prime\), so \(m=m^\prime\), so these coefficients are unique.

Future projects

This article is just the beginning --- there are many other directions you could go in exploring empirical Pokémon typing. Some future directions I'm interested in are:

• Type inference from learned attacks. Which attacks give you the most information about a Pokémon's type? Do those attacks share a type with the Pokémon or not?
• Additive trees If you use various Pokémon traits (such as evolution strategy, learned movesets, etc.) to define a distance metric between species, do they cluster into clearly-delineated types?
• Informational bounds Given the existing type system (as opposed to a theoretically possible alternative type system), how much information do you need in order to reliably reconstruct the susceptibility table? How likely are two types to appear the same, due to coincidentally measuring points where their susceptibilities overlap? What's the worst case scenario in terms of failing to distinguish two different types, and how likely is that scenario?
• Type triage / decision trees Design the most efficient battery of susceptibility tests to determine the type of a never-before-seen Pokémon. A greedy (potentially non-optimal) decision tree covering all pairs of seventeen types is available [[http://logical.ai/guess/allergy/][here]]; note that it has a fun in-universe presentation. It takes seven questions in the worst (normal-steel) case.

What is the shape of attraction? To find out, we can make a diagram out of string and pushpins. Suppose—reductively, but for simplicity—that there are two genders and three types of attraction: same-gendered, both-gendered, and different-gendered. Altogether, we have six different pushpins corresponding to these six different identities:

We can start by drawing arrows of attraction from each identity to the identities it's potentially attracted to. You can try this exercise yourself. When I do it, I get the following diagram:

Of course, some of these attractions are unrequited—there's an arrow going one way but not the other. If we get rid of those unrequited attractions, the resulting diagram depicts the shape of mutual attraction:

Beautiful, isn't it?

Such a diagram also makes it clear how many degrees of separation there are between different identities—can you see which identities are separated by the longest path? Hint: There are three identity pairs that are maximally separated. You'd have to form a long chain of relationships to get people with those identity pairs into a relationship-by-transitivity with each other.

Also—take heart: No matter what your identity is, two out of three identities you're attracted to are attracted to you in return.

Three genders

You can extend this approach to multiple discrete genders: G is your set of available genders and \(2^G\)—the set of all combinations of genders—is your available orientations. When G=3, there are 8 possible orientations, making 24 total identities. The mutually compatible relationship graph (like the one drawn above) looks like this:

This is a graph of mutual attraction between three genders. Each dot represents an identity (gender + orientation combo). Edges represent mutual compatibility. The three genders are symmetrically arranged in three kite-shaped regions containing the eight possible orientations. Orientations consist of attraction to some combination of your own gender, the gender clockwise from you, and the gender counterclockwise from you (imagine the genders have some rock-paper-scissors clockwise order.) If you like, you can figure out which orientation is which by looking at their connections. Otherwise, here's the complete description.

Taking the topmost kite as an example, the eight orientations—from top to bottom and left to right—are:

1. self only (white dot at top);
2. no attraction (disconnected black dot);
3. self-or-widders (leftmost white dot);
4. self-or-sunward (rightmost white dot);
5. widders-only (leftmost black dot);
6. sunward-only (rightmost black dot);
7. widders-or-sunward (middle black dot);
8. widders-sunward-self (white dot at bottom).

Instead of drawing a loopy edge for own-gender orientations, I use white dots. Edge color and thickness helps you read the graph, but don't otherwise mean anything. Some interesting observations:

1. The orientations within each gender form a cube, with each axis direction representing another gender and each face being totally connected with the face of the neighboring cube on that side—you might be able to see it here by imagining that the white dots are raised out of the plane.
2. When you try to connect two separate non-ace identities through a chain of mutual compatibility links, then no matter how many genders there are, you need at most four identities total: e.g. the starting identity, a pan person whom the starting identity likes, a pan person whom the ending identity likes, and the ending identity. (So the graph diameter of the connected part is always 3, regardless of the number of genders.)
3. With the two-gender (G=2) picture at the start of this article, we didn't include ace identities (identities with no links in the graph). Now that this G=3 picture includes them, we see more reasonably that half the identities you're attracted to are attracted to you in return (regardless of G).
4. The two-gender compatible relationship graph is, as you'd expect, contained in the three-gender compatible relationship graph:

I've been thinking a lot recently about how to cross the street. Specifically, when standing at the position labeled START in the map shown here, what's the best way to get to the position labeled HOME?

There are two main strategies that I know some people employ:

1. Disregarding: Never cross at the first vertical crosswalk. Instead, always proceed to the second crosswalk.
2. Opportunism: If the first vertical crosswalk is available when you arrive, cross there. Otherwise, proceed to the second crosswalk.

Interestingly, I asked around and found that both Disregarding and Opportunism are popular strategies — and that advocates of one consider their own strategy to be obviously superior:

Disregarder: “By proceeding to the second crossing, you can cross in whichever direction is available, then cross in the other direction immediately afterwards. It's more efficient if you don't have to wait for the right direction to become available.”

Opportunist: “By crossing immediately, you take the opportunity to bring yourself closer to your goal right away; it's more efficient if you have to wait for only one light rather than two.”

I decided to find an analytic solution, which led to some beautiful graphs— and an unexpected verdict.

(Which strategy do you think is better? Are they equally efficient?)

The crosswalk model

Here are some of the main features of my model:

• Each crosswalk switches between horizontal and vertical with a cycle time of S seconds.
• You take a constant amount of time T seconds to cross any street. (For example, you don't sprint to make it across the street in time.)
• You take less than one cycle time to cross the street. 0<T<S
• At the second crosswalk, there is no "dead time" where no one can walk. (In practice, dead time would be used to allow cars to make turns against the direction of traffic.)
• The first and second crosswalk have independent cycles.

Depictions of crossing strategies

When you wait to cross the street both directions

In this image, you see all possible outcomes of crossing the street twice consecutively. The horizontal axis records the state of the crosswalk, which alternates between allowing horizontal and vertical crossings. The vertical axis measures the activity of a person over time — the person's arrival is marked at the top of the image, and time proceeds downward. As the person's time advances, so does the state of the crosswalk — so individuals are represented by lines at a 45° angle.

Each diagonal line represents a single individual who has arrived at the crosswalk when it's in a particular state. As the person waits and walks, their line changes color. For example, the leftmost line in the image represents the worst case scenario: the person arrives having not enough time to cross, and so must wait (grey segment). When the light changes, the person crosses (green segment). Afterwards, the person waits for the current cycle to finish (red segment) so as to cross in the other direction next (blue segment).

Here are some interesting observations about waiting times in this scenario:

• The grey region has width and height equal to your crossing time T, because you only miss the light if it has fewer than T seconds remaining.
• The image is periodic in the horizontal direction with period S, because the state of the crosswalk is periodic.
• The red region has a 90° corner because if you must wait for a new cycle to begin, you'll spend T seconds walking across, and the full remainder of the cycle S−T seconds waiting for the light to change. On the other hand, if you arrive after the cycle has started, you'll spend T seconds walking across, and less than the full cycle waiting.
• (!) The waiting-time regions (red and grey) align perfectly, forming triangular regions of width and height S. This is because the first waiting time is at worst T, and the second waiting time is at worst S−T.
• As a corollary, average waiting time in the second crossing strategy is independent of walking speed; the gain from crossing the street quickly is cancelled by the fact that you'll have to wait that much longer for the cycle to complete once you've reached the other side.

When you must cross the street in only one direction

In the case where you can't cross at the first crosswalk, the Opportunist and the Disregarder follow the same strategy: they proceed to the second crosswalk and cross as efficiently as possible.

So, if there is to be any difference in waiting times between the two strategies, it must appear when it's genuinely possible to cross the street — when the Opportunist chooses to cross, and the Disregarder chooses not to.

In that case, the Opportunist can cross in one direction immediately, spending no time waiting at all. Then, at the second crosswalk, the Opportunist's outcomes look like this:

The worst case scenario is when the Opportunist arrives during the tail end of the cycle which they need to take — they have no time to cross, and must wait for one complete cycle in the wrong direction before they can cross. The best case, occurring prevalently, is when they arrive sometime during the cycle which they need to take and hence wait no time at all to cross the second time.

The waiting time area for the Opportunist is sum of the areas of the red and grey regions; they form a triangle of width S+T.

Average waiting time

Here, we'll compute the average waiting time of each strategy to get a better feel for the difference.

The waiting time area for a Disregarder is S2. The waiting time area for an Opportunist depends on whether they were able to cross at the first crosswalk or not: if they were able, the waiting time area is 12(S+T)2, the area of the triangle in the previous section. If they weren't able to cross at the first crosswalk, they behave like a Disregarder would, with a waiting time area of S2.

How often will the Opportunist be able to cross at the first crosswalk? The crosswalk has a period of length 2S. S of those seconds are uncrossable because the light is in the wrong direction; T of those seconds are uncrossable because there isn't enough time to cross even though the light is in the right direction. The rest of the time, the Opportunist can cross. That's S−T out of 2S.

The average waiting time occurs when we divide the waiting-area by the period 2S. Thus the Disregarder's average waiting time is \(\)

S22S=S/2,half of a cycle. The Opportunist's average waiting time is a weighted average:12S⎡⎣⎢⎢⎢S−T2S⋅(S+T)22taken opportunity+S+T2S⋅S2missed opportunity⎤⎦⎥⎥⎥.

The difference in average waiting time for these two strategies is

Δ=12SS−T2S[S2−(S+T)22]which is positive if Opportunism is better, and negative if Disregarding is better. To simplify the expression, defineβ≡T/S, where0<β<1by assumption. Then the difference in average waiting time is:Δ====12SS−T2S[S2−(S+T)22]12S(1−β)S2S[S2−S2(1+β)2/2]S8(1−β)[2−(1+β)2][β3+β2−3β+1]S

The Verdict

In fact, the difference in waiting time varies depending on β, the fraction of the cycle time you take to cross the street.

\( \Delta = [\beta^3 + \beta^2 - 3\beta + 1]S \)

The Disregarder and Opportunist are equally efficient when this quantity is zero; that is, when β=2√−1≈41%. For shorter walking times, Opportunism is better. For longer walking times, Disregarding is better.

Intuitively, this occurs because the Opportunist can control the size of the window of opportunity by walking faster. In contrast, any advantage the Disregarder gets from walking faster is cancelled by the additional time spent waiting for the cycle to end.

This surprising result has an interesting consequence: Suppose two people walk at the same speed. One of them has to cross the street in one direction, the other has to cross in two directions. Who will take longer, on average? The answer, assuming they don't jaywalk, is that it depends on what their shared walking speed is.

♡2015 Dylan Holmes. My work here (including this HTML file, and plotter.js) is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. (This means that you are free to use, modify, and re-distribute this work—even commercially—as long as you attribute the original to me and share your modified versions in the same way.)