Step into Computational Geometry: Notebook III.

Abstract

In this notebook we present a collection of three new results in planar computational geometry. The first problem is to test a given n-vertex simple polygon for monotonicity; this problem can be optimally solved in time theta(n). The second result is an improved algorithm for the rectangle enclosure problem; this algorithm improves over an existing one by using optimal space theta(n). Finally, the third result is the construction, in time 0(nlogn), of the shortest path between two points in the interior of an n-vertex polygon P, when the path is constrained to lie within P. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1981
Accession Number
ADA124461

Entities

People

  • Franco P. Preparata

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Air Platforms
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Boundaries
  • Computational Complexity
  • Computer Programming
  • Computers
  • Construction
  • Electronics
  • Four Dimensional
  • Geometry
  • Information Processing
  • Polygons
  • Preprocessing
  • Sequences
  • Three Dimensional
  • Triangles
  • Two Dimensional

Fields of Study

  • Mathematics

Readers

  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Marine Hydrodynamics
  • Mathematical Modeling and Probability Theory.

Technology Areas

  • Space
  • Space - Spacecraft Maneuvers