# Geofencing Time Complexity Analysis

`q := Point QueryC := Number of citiesV := Number of vertices that define a city boundaryn := Number of fence polygons in a cityv := Number of vertices in a fence polygon `

## Brute Force

`Brute() -> O(Cnv)`

## Augmented Brute Force

`Uber() -> O(CV) + O(nv)`

## RTree

`M := Maximum number of childrenRtree() -> O(logM(Cn)) + O(v)`

## S2

`T := Features with cell labelQTree() -> O(T) + O(v)`

## Comparison

`q := Point QueryC := Number of citiesV := Number of vertices that define a city boundaryn := Number of fence polygons in a cityv := Number of vertices in a fence polygonBrute() -> O(Cnv)              Uber()  -> O(CV) + O(nv)       Rtree() -> O(logM(Cn)) + O(v)  Qtree() -> O(T) + O(v)       `

## Estimating

`C := 100 // citiesV := 100 // vertices in cityn := 100 // polygons in cityv := 100 // vertices in polygonM := 50  // rtree parameterT := 4   // polygons per cellBrute() -> 1   * 10^6Uber()  -> 2   * 10^4Rtree() -> 2.3 * 10^2Qtree() -> 4   * 10^2`

## Thinking inside the box

`BruteBox() -> O(Cn) + O(v)              -> 1 * 10^4UberBox()  -> O(C) + O(V) + O(n) + O(v) -> 4 * 10^2`

# Benchmarking Geofencing Algorithms

`type GeoFence interface {    Add(f *geo.Feature)    Get(c geo.Coordinate) []*geo.Feature}`
`func BenchmarkFence(b *testing.B) {    fence := geofence.NewFence()    for _, tract := range tracts {        fence.Add(tract)     }    b.ResetTimer()    for n := 0; n < b.N; n++ {          result = fence.Get(museums["old whitney"])    }}`