### Abstract

Three techniques in computational geometry are explored: Scaling solves a problem by viewing it at increasing levels of numerical precision; acHvat/ovt is a • restricted type of update operation, useful in sweep algorithms; the CaTtex'hzR tree is a data structure for problems involving maximums and minimums. These techniques solve the minimum spanning tree problem in R and ] in O(zz(lg n)rlg lg n) time and O(n) space, where for Rk∞ and k ≥3, r =k-2; for Rk1, r = 1,2,4 for k =3,4,5 and r =k for k >5. Other problems solved include Rk1 and Rk all nearest neighbors, post office and maximum spanning tree; Rk maxima, Rk rectangle searching problems, and Zpk all nearest neighbors (1≤p≤∞).

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC 1984 |

Publisher | Association for Computing Machinery |

Pages | 135-143 |

Number of pages | 9 |

ISBN (Electronic) | 0897911334 |

DOIs | |

State | Published - Dec 1 1984 |

Externally published | Yes |

Event | 16th Annual ACM Symposium on Theory of Computing, STOC 1984 - Washington, United States Duration: Apr 30 1984 → May 2 1984 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 16th Annual ACM Symposium on Theory of Computing, STOC 1984 |
---|---|

Country | United States |

City | Washington |

Period | 4/30/84 → 5/2/84 |

### All Science Journal Classification (ASJC) codes

- Software

## Fingerprint Dive into the research topics of 'Scaling and related techniques for geometry problems'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC 1984*(pp. 135-143). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/800057.808675