Affordable Access

Publisher Website

A counterexample to an algorithm for computing monotone hulls of simple polygons

Authors
Journal
Pattern Recognition Letters
0167-8655
Publisher
Elsevier
Publication Date
Volume
1
Issue
4
Identifiers
DOI: 10.1016/0167-8655(83)90028-4
Keywords
  • Convex Hull
  • Monotone Hull
  • Maximal Polygons
  • Simple Polygons
  • Weakly Externally Visible Polygons
  • Algorithms
  • Complexity
  • Computational Geometry
  • Pattern Recognition
Disciplines
  • Computer Science

Abstract

Abstract A two-stage algorithm was recently proposed by Sklansky (1982) for computing the convex hull of a simple polygon P. The first step is intended to compute a simple polygon P ∗ which is monotonic in both the x and y directions and which contains the convex hull vertices of P. The second step applies a very simple convex hull algorithm on P ∗ . In this note we show that the first step does not always work correctly and can even yield non-simple polygons, invalidating the use of the second step. It is also shown that the first step can discard convex hull vertices thus invalidating the use of any convex hull algorithm in the second step.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

A counterexample to a diameter algorithm for conve...

on IEEE Transactions on Pattern A... March 1982

Computing simple-path convex hulls in hypergraphs

on Information Processing Letters Jan 01, 2011

A simple and fast incremental randomized algorithm...

on Computational Geometry Jan 01, 1991
More articles like this..