A Novel Type of Skeleton for Polygons

A new internal structure for simple polygons, the straight skeleton, is introduced and discussed. It is composed of pieces of angular bisectores which partition the interior of a given n-gon P in a tree-like fashion into n monotone polygons. Its straight-line structure and its lower combinatorial complexity may make the straight skeleton preferable to the widely used medial axis of a polygon. As a seemingly unrelated application, the straight skeleton provides a canonical way of constructing a polygonal roof above a general layout of ground walls.

• Publication year

  1995

• Venue

  Journal of universal computer science (Online)

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.3217/jucs-001-12-0752
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Voronoi diagrams—a survey of a fundamental geometric data structure

  1991cited by this paper
• Medial Axis Transformation of a Planar Shape

  1982cited by this paper
• Efficient computation of continuous skeletons

  1979cited by this paper

• Flat Tessellations in Search of a Dome Shape

  2025cites this paper
• Polygon decomposition for obstacle representation in motion planning with Model Predictive Control

  2025cites this paper
• Semantics-based connectivity graph for indoor pathfinding powered by IFC-Graph

  2025cites this paper
• Offset Geometric Contact

  2025cites this paper
• Minimum Partition of Polygons under Width and Cut Constraints

  2025cites this paper
• A combinatorial algorithm for finding straight skeleton of a digital object

  2025cites this paper
• Constructing Efficient Algorithms for Solving Certain Computational Geometry Problems Using Reeb Graphs

  2025cites this paper
• Procedural Generation of Guard Paths in Stealth Games Using Level Geometry

  2025cites this paper
• Structural Tree Extraction from 3D Surfaces

  2025cites this paper
• Spatial circulatory networks based on the peripheral medial axis transform

  2024cites this paper
• Generating 3D House Wireframes with Semantics

  2024cites this paper
• The rigid and flat-foldable kirigami cubes

  2024cites this paper
• The Challenges of Line Buffers: Issues and Methods

  2024cites this paper
• Real-Time Procedural Generation with GPU Work Graphs

  2024influential citation
• From knowledge encoding to procedural generation for early-stage layout design: A case of linear shopping centres

  2024cites this paper
• 2D Skeleton-Based Keypoint Generation Method for Grasping Objects with Roughly Uniform Height Variation

  2023cites this paper
• Geometric Shape Characterisation Based on a Multi-Sweeping Paradigm

  2023cites this paper
• Optimal multiobjective design of guidance information systems in underground spaces: Model development and a transportation hub case study

  2023cites this paper
• Full Coverage of Confined Irregular Polygon Area for Marine Survey

  2023cites this paper
• Deep learning aided web-based procedural modelling of LOD2 city models

  2023cites this paper
• Polygon vector map distortion for increasing the readability of one-to-many flow maps

  2023cites this paper
• BIM-based automated design for HVAC system of office buildings—An experimental study

  2022cites this paper
• Progressive Collapse of Dual-Line Rivers Based on River Segmentation Considering Cartographic Generalization Rules

  2022cites this paper
• Skeleton line extraction for areal hydrographic elements considering spatial and hierarchical relationships

  2022cites this paper
• A Closer Cut: Computing Near-Optimal Lawn Mowing Tours

  2022cites this paper
• Confined Water Body Coverage under Resource Constraints

  2022cites this paper
• Roof Segmentation Towards Digital Twin Generation in LoD2+ Using Deep Learning

  2022cites this paper
• Building Model Generation Framework Based on Wave Function Collapse

  2022cites this paper
• A Framework for Extracting Abstracted Route Graphs Toward Air Traffic Flow Modeling

  2022cites this paper
• Tiling billiards and Dynnikov’s helicoid

  2021cites this paper
• Implementing straight skeletons with exact arithmetic: Challenges and experiences

  2021cites this paper
• Voronoi Diagrams

  2021cites this paper
• Explicit control of 2D and 3D structural complexity by discrete variable topology optimization method

  2021cites this paper
• Roof Damage Assessment from Automated 3D Building Models

  2021influential citation
• An explicit and implicit hybrid method for structural topology optimization

  2021cites this paper
• Modeling Coverage Areas of Anisotropic Transmitters by Voronoi-like Structures

  2021cites this paper
• Intuitive and efficient roof modeling for reconstruction and synthesis

  2021influential citation
• An Automated Approach to Coastline Simplification for Maritime Structures with Collapse Operation

  2021cites this paper
• A partitioned collapse method for long and narrow patches

  2021cites this paper
• Routing of fluidic circuits using skeletons of polygonal figures

  2020cites this paper
• From Historical Newspapers to Machine-Readable Data: The Origami OCR Pipeline

  2020cites this paper
• Enabling the Development and Implementation of Digital Twins: Proceedings of the 20th International Conference on Construction Applications of Virtual Reality

  2020influential citation
• BIM-based automated determination of exit sign direction for intelligent building sign systems

  2020cites this paper
• Roof Geometry in Building Design

  2020cites this paper
• Continuous toolpath planning in a graphical framework for sparse infill additive manufacturing

  2020cites this paper
• A progressive method for the collapse of river representation considering geographical characteristics

  2020cites this paper
• Between Shapes, Using the Hausdorff Distance

  2020cites this paper
• Procedural Generation of Multistory Buildings With Interior

  2020cites this paper
• A Method for Generating the Centerline of an Elongated Polygon on the Example of a Watercourse

  2020cites this paper
• On Implementing Straight Skeletons: Challenges and Experiences

  2020cites this paper
• Mitered Offsets and Skeletons for Circular Arc Polygons

  2020cites this paper
• Generating straight skeleton-based navigation networks with Industry Foundation Classes for indoor way-finding

  2020cites this paper
• The Algorithm Design Manual

  2020cites this paper
• An Optimized Algorithm for Computing the Voronoi Skeleton

  2020cites this paper
• Algorithm of Micro Mouse

  2020cites this paper
• Step-By-Step Straight Skeletons

  2020cites this paper
• A-Mazer with Genetic Algorithm

  2020cites this paper
• Topology-aware Camera Control for Real-time Applications

  2020cites this paper
• An improved partitioning method for dissolving long and narrow patches

  2020cites this paper
• Experimental Evaluation of Straight Skeleton Implementations Based on Exact Arithmetic ∗

  2020cites this paper
• Exploring procedural generation of buildings

  2020cites this paper
• Volume Optimization of Solid Waste Landfill Using Voronoi Diagram Geometry

  2019cites this paper
• Continuous Toolpath Planning in Additive Manufacturing

  2019cites this paper
• Recognizing Geometric Trees as Positively Weighted Straight Skeletons and Reconstructing Their Input

  2019cites this paper
• New Applications of the Nearest-Neighbor Chain Algorithm

  2019cites this paper
• CSRN 2901-WSCG 2019 proceedings, Part I

  2019cites this paper
• Esqueletos retilíneos de polígonos e poliedros

  2019influential citation
• On topology optimization with elliptical masks and honeycomb tessellation with explicit length scale constraints

  2019cites this paper
• Selected open problems in Matching Under Preferences

  2019cites this paper
• Computing the Straight Skeleton of an Orthogonal Monotone Polygon in Linear Time

  2019cites this paper
• New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs

  2019cites this paper
• A Path Planning Method for Robotic Wire and Arc Additive Manufacturing of Thin-Walled Structures with Varying Thickness

  2019cites this paper
• A Modified Methodology for Generating Indoor Navigation Models

  2019cites this paper
• Voronoi diagram of orthogonal polyhedra in two and three dimensions

  2019cites this paper
• Optimization Heuristics for Computing the Voronoi Skeleton

  2019cites this paper
• ALGORITHM FOR SELECTING STRUCTURAL ELEMENTS IN A SEGMENTED IMAGE PRESENTED IN THE FORM OF A FOREST GRAPH

  2019cites this paper
• Extracting Centerlines From Dual-Line Roads Using Superpixel Segmentation

  2019cites this paper
• Euclidean TSP, Motorcycle Graphs, and Other New Applications of Nearest-Neighbor Chains

  2019cites this paper
• Hai Huang Bayesian Models for Pattern Recognition in Spatial Data

  2018cites this paper
• Grammar-guided reconstruction of semantic 3D building models from airborne LiDAR data using half-space modeling

  2018cites this paper
• User assisted and automatic inverse procedural road modelling at the city scale

  2018cites this paper
• Improved Jitter Elimination and Topology Correction Method for the Split Line of Narrow and Long Patches

  2018cites this paper
• Straight Skeletons and Mitered Offsets of Polyhedral Terrains in 3D

  2018cites this paper
• Optimization strategies for robotic additive and subtractive manufacturing of large and high thin-walled aluminum structures

  2018cites this paper
• Seeing structure: Shape skeletons modulate perceived similarity

  2018cites this paper
• Automatic Generation of 3D Building Models for Environmental Education by Straight Skeleton Computation

  2018influential citation
• Domain specific methods for procedural modeling of historical architecture

  2018cites this paper
• A Static Moment for a Polygon and Its Applications

  2018cites this paper
• Computing positively weighted straight skeletons of simple polygons based on a bisector arrangement

  2018cites this paper
• Min-/Max-Volume Roofs Induced by Bisector Graphs of Polygonal Footprints of Buildings

  2018cites this paper
• Euler Transformation of Polyhedral Complexes

  2018cites this paper
• Roof report from automatically generated 3D building models by straight skeleton computation

  2018influential citation
• Mitered offsets and straight skeletons for circular arc polygons

  2018cites this paper
• Building Polygon Rectification for Automated 3D Building Models

  2018cites this paper
• Geometric Constraint Model and Mobility Graphs for Building Utilization Intelligence

  2018cites this paper
• On merging straight skeletons

  2018cites this paper
• Optimization strategies for robotic additive and subtractive manufacturing of large and high thin-walled aluminum structures

  2018cites this paper
• Simplifying Urban Data Fusion with BigSUR

  2018cites this paper
• Skeletal Structures for Modeling Generalized Chamfers and Fillets in the Presence of Complex Miters

  2018cites this paper
• Area collapse algorithm computing new curve of 2D geometric objects

  2017cites this paper