### Abstract

Given a set of points P - {p1,p2....Pn} ,n three dimensions, the width of P, W(P)% is defined as the minimum distance between parallel planes of support of P. It is shown that W(P) can be computed in O(n logn time and O(n) space, where / is the number of antipodal pairs? of edges of the convex hull of P, and in the worst case O(n^{2}). [f P is a set of points in the plane, this complexity can be reduced to O(n logn). Finally, for simple polygons linear time suffices.

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

Title of host publication | Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985 |

Publisher | Association for Computing Machinery, Inc |

Pages | 1-7 |

Number of pages | 7 |

ISBN (Electronic) | 0897911636, 9780897911634 |

DOIs | |

State | Published - Jun 1 1985 |

Event | 1st Annual Symposium on Computational Geometry, SCG 1985 - Baltimore, United States Duration: Jun 5 1985 → Jun 7 1985 |

### Publication series

Name | Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985 |
---|

### Other

Other | 1st Annual Symposium on Computational Geometry, SCG 1985 |
---|---|

Country | United States |

City | Baltimore |

Period | 6/5/85 → 6/7/85 |

### ASJC Scopus subject areas

- Computational Mathematics
- Geometry and Topology

## Fingerprint Dive into the research topics of 'Computing the width of a set'. Together they form a unique fingerprint.

## Cite this

Houle, M. B., & Toussaint, G. T. (1985). Computing the width of a set. In

*Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985*(pp. 1-7). (Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985). Association for Computing Machinery, Inc. https://doi.org/10.1145/323233.323234