Arrow Research search

Author name cluster

Marshall W. Bern

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers
2 author rows

Possible papers

13

TCS Journal 1992 Journal Article

Fast geometric approximation techniques and geometric embedding problems

  • Marshall W. Bern
  • Howard J. Karloff
  • Prabhakar Raghavan
  • Baruch Schieber

Given an undirected n-vertex graph G and a set of n points in R d, we wish to embed the vertices of G onto the points so as to minimize the total embedded edge length. Important special cases of this geometric embedding problem as those in which G is a binary tree, a cycle, or a star. We give fast approximation algorithms for embedding these graphs on the line and in the plane in several metrics. Our principal techniques are: a notion of “approximate geometric sorting” that can be computed in linear time, and fast approximation schemes for the minimum spanning tree problem in the plane. We expect that these approximation techniques can be applied to many geometric problems besides the embedding problem. We give the example of approximating the convex hull of a set of points in the plane.

Details DOI

FOCS Conference 1990 Conference Paper

Provably Good Mesh Generation

  • Marshall W. Bern
  • David Eppstein
  • John R. Gilbert

Several versions of the problem of generating triangular meshes for finite-element methods are studied. It is shown how to triangulate a planar point set or a polygonally bounded domain with triangles of bounded aspect ratio, how to triangulate a planar point set with triangles having no obtuse angles, how to triangulate a point set in arbitrary dimension with simplices of bounded aspect ratio, and how to produce a linear-size Delaunay triangulation of a multidimensional point set by adding a linear number of extra points. All the triangulations have size within a constant factor of optimal and run in optimal time O(n log n+k) with input of size n and output of size k. No previous work on mesh generation simultaneously guarantees well-shaped elements and small total size. >

Details

FOCS Conference 1985 Conference Paper

Why Certain Subgraph Computations Require Only Linear Time

  • Marshall W. Bern
  • Eugene L. Lawler
  • A. L. Wong

A general problem in computational graph theory is that of finding an optimal subgraph H of a given weighted graph G. The matching problem (which is easy) and the traveling salesman problem (which is not) are well known examples of this general problem. In the literature one can also find a variety of ad hoc algorithms for solving certain special cases in linear time. We present a general methodology for constructing linear time algorithms in the case that the graph G is defined by certain rules of composition (as are trees, series parallel graphs, and outerplanar graphs) and the desired subgraph H satisfies a "regular" property (such as independence or matching). This methodology is applied to obtain a linear time algorithm for computing the irredundance number of a tree, a problem for which no polynomial time algorithm was previously known.

Details
v2026.09.13